glow's blog

Another ad-hoc string problem
By glow, history, 6 years ago, In English

A string is called beautiful if string S = T + T. You're given a string find length of longest beautiful subsequence in given string.

Constraints : 1 <= length(S) <= 100

PS: Ihave no clue except try all numbers with k bits set and like bit-mask check if it's beautiful. Of-course you take k even and start from biggest possible k ie. length(S) - (length(S) & 1). Any hints on this ?

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Main observation is: all letters of first part will be located earlier than any letter of second part.

Let's we fixed k as first index where only letters from second part could be. Now dynamic programming could be used:

dp[i][j] — maximal length of beautiful subsequence where first part ends in i (or earlier) and second in j (or earlier) (1 ≤ i < k ≤ j ≤ n).

This dp could be calculated in O(|S|2):

  • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  • if s[i] = s[j]: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1).

Total complexity of solution is O(|S|3) that should easily fit with |S| ≤ 100.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    That's just came to my mind while I was relaxing a while ago.. dayummmmnn... In other words keep left rotating a copy of original string and for every left rotation find LCS, update answer with ans = max(ans,current_LCS/2)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe I misunderstood you, but maximal LCS of string S and any of its rotations has length |S| - 1 ('abcde' and 'bcdea').

      Main idea is separate two parts of answer in one string.

      → Reply