@p1p5_5 i saw your solution lcs part is correct but you should do that consecutive diffrent character only in string implementation before LCS in o(n) and after that lcs it will give correct answer and also optimize your dp part(LCS) in most cases except case (abcdefghi…wxyz) because no consecutive same character.
and then f(a)+f(b)-lcs(a,b) will give correct answer.
you can check my code link .if any problem persist you can ask
@harrypotter0 you can do this in any programming language by below steps:-
step 1:-process both sting A and String B such that no consecutive similiar character exsist.for
example abbaaccde would be abacde after processing.it will take o(n) time where n is length of string
step 2:-compute LCS of processed strings using Dynamic Programming in o(nm) time where n is length of processed String A and m is length of processed string B.LCS computed is length of longest sequence.
step 3:-answer will be length of processed string A+length of processed string B-LCS
@vijju123 I really think that adding the clause to output the resulting string wouldn’t have made things much tougher…
- Compress the input strings by removing consecutive duplicate letters.
- Find the lcs(a, b) and from the expression mentioned compute the minimum value.
- Keep track of the next character in lcs(a, b) and erase characters from the input string until the head characters are both equal to the next character in lcs(a, b).
I haven’t coded it up yet but I’m sure that it or a very minor variation of it might work.
True- I never meant that adding that clause was to make it tougher. Point was, seeing his dp states and table I thought it would have been a nice addition to the problem.
@sapfire @vijju123 some tweaking for x =1 and x=2 with lcs approach got me AC on this one . But can anyone explain to me the D.P. approach , I am clueless on that .
@abhi55 Thanks for answering my doubt. I understood the part of optimization of my LCS function but I did not exactly understood the first part. " but you should do that consecutive diffrent character only in string implementation before LCS in o(n) and after that lcs it will give correct answer" Can you please explain this again? Sorry for this, I did not get my mistake in the program. I have found out LCS including repetition but my function “findCharacters(String)” will always return be the number of indices satisfying Ci≠Ci+1.
I have done an implemenation of dp on the similar lines of editorial and I can’t seem to think of a case where it fails but it is failing while submitting.
dp[i][j][k] represents, I have taken i characters from string1 and j characters from string2 and the last character is from stringk
i am saying that suppose you have string aabccdee now you can see that consecutive same character will make no change in total cost like in above string you first minimize it in abcde by removing repition of same character which are consecutive in o(n) then perform LCS part on it