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

kas 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 ini(or earlier) and second inj(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]);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.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.