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 ?
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):
Total complexity of solution is O(|S|3) that should easily fit with |S| ≤ 100.
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)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.