I was trying to solve problem from SRM 698. I can’t think of any approach for this problem. Firstly I thought, lets iterate through 0 to n … and see if i delete i character from string will I get S = T + T …but after some time I realised it’s difficult to keep track which characters to be deleted and so on… Recently in Educational Round at Codeforces I got another problem… I keep getting these types of problems all the time but never solved them . Can you please help me developing an approach for all these types of problems where they delete, insert and do all kind of operations like this problem…
Also could not find editorials for that match… if you find please share the link …
1 Like
@hulk_baba you can solve SRM 698 problem by iterating over all possible combinations for string T, i.e., you can divide string S in two substrings and then find the length of maximum LCS for all those combinations.
3 Likes
Can you please elaborate? I mean, when you say we can iterate over all possible combinations for T, then doesn’t the time complexity increases too much?
Kindly show us your viewpoint 
@hulk_baba the first and third problems are somewhat similar, but the second one is quite different.
RepeatStringEasy from SRM 698 can be solved just as @srd091 describes. The longest square subsequence of a string s is made up of two identical substrings joined together. So if you split s into two pieces, the longest common subsequence of the two pieces would give you one such square subsequence. If you try splitting it in all possible indices, there are only |s|-1 such ways, and finding the LCS of the two halves you get each time, 2\;\times the maximum value of all the LCS computed would be the answer to the whole problem. The complexity would be \mathcal{O}(|s|^3), which is good enough as |s| \le 50.
For the Codeforces problem Two strings I found some hints here, by clicking on the “Tutorial” at the bottom-right of the page.
The p and s arrays as described can be filled in linear time. If the portion of the string to be kept is [0..i] and [j..len(b)-1] then the answer can be obtained by binary searching for j for each i and seeing which [i+1..j-1] is of least length. If you get stuck with the implementation you can take a look at my code. The complexity is \mathcal{O}(|s|\;log\;|s|).
RepeatString requires you to change the given string s into a square string, which is made up of two identical strings. So once again you can split s into two pieces, and the minimum number of operations required to change one piece into the other can be computed. It is called the edit distance (more specifically the Levenshtein distance) of the two strings. Iterating over all possible ways to split s and taking the minimum of all such edit distances computed will give you the answer to the whole problem. This can be done in \mathcal{O}(|s|^3) just like RepeatStringEasy.
Do ask if something is not clear
2 Likes
@vijju123 there will be total (|S|-1) possible combinations, so the overall complexity of the program will be O(|S|^{3}) and as the constraints are very small (|S|<=50), so it won’t result in TLE.
Thanks @meooow for the help, I got the first one accepted. Now I am going to try second and third…Will surely ask you if something is not clear.
Thanks @srd091 for the help, I got that Accepted. Is that the best complexity we can achieve? What is your advice on other parts of my question ?
Oh!!
Thanks for explaining!!
Yeah, it was O(S^3).
Actually, even I am curious if its the best time complexity we can achieve in this Q? Can you answer it?
@meooow I tried to implement what I grapsed from tutorial you mentioned…I firstly tried to find the indices of prefix for b from a and similarly indices of suffix. I then check if they overlap or not…
The things I realised if causing WA is it may be possible that the prefix I calculated may not be the best one…I don’t know whether I conveyed myself clearly. Have a look at my
[1] . Please help me to debug this ..also interestingly I found one dp solution but I don't get it very much. please see this [also][2] .
[1]: http://codeforces.com/contest/762/submission/24242771
[2]: http://codeforces.com/blog/entry/49997#comment-339626Hey @hulk_baba, your solution has 2 bugs. First of all your interruption case is unnecessary and ends up giving WA for cases like this. And second, you did not consider the case where the entire suffix might be longer than some prefix + some suffix, such as this.
The dp solution is very neat. In the dp solution the prefix and suffix arrays are made with respect to a and not b. So pre[i] is the size of the largest prefix of b that is a subsequence of a[0..i] and suf[i] is the size of the largest suffix of b that is a subsequence of a[i..len(a)-1]. We want to maximize the sum of the lengths of the prefix and suffix such that they don’t intersect, which is the same as finding the maximum value of pre[i]+suf[i+1].
(I would have put this in the comment but it exceeds the character limit)
2 Likes
For me it’s not easy to debug my own solution so, I saw solutions of other coders and found a good implementation and got it accepted. Thank you @meooow for your help on dp solution…
Sure
If I may suggest something, try to make your code concise. If a solution becomes long is it is easier to make a mistake and harder to debug. Don’t keep parts that are unnecessary and sometimes it is even possible to avoid handling an edge case. For example in this problem if you add a character, suppose “a”, to the start and end of both a and b you will not have to deal with the case where there is no common prefix or suffix. Hope this helps!
1 Like