### glow's blog

By glow, history, 3 weeks ago, ,

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 ?

•
• +16
•

 » 3 weeks ago, # |   +1 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.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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)
•  » » » 3 weeks ago, # ^ |   0 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.