glow's blog

By glow, history, 15 months 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

 » 15 months 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.
•  » » 15 months 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)
•  » » » 15 months 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.
 » 7 months ago, # |   0 This code works . s = "abfeabe" op = 0 ; s = "vvabeabeff" op = 6 private static int beautifulStringLen(String s) { int len = s.length(); if (len <= 1) { return 0; } boolean[][] dp = new boolean[len+1][len+1]; int max = 0; for (int i = 0 ; i < len ; i++) { for (int l = 1; l <= len ; l++) { int j = i +l; if (j >= len) { break; } if (s.charAt(i) == s.charAt(j)) { dp[i][j] = true; if (i-l+1 >= 0 && dp[i-l+1][j-l+1]) { max = Math.max(max, l); } } } } // print(dp); return max*2; }