In the problem is given a string containing, ‘c’ or ‘+’. A Complete String is a non-empty string that consists of consecutive occurrences of “c++”, any number of times.
You can form a Complete String (if possible) by removing some of the characters from the string (possibly 0). Your task is to remove minimum number of the characters from the string (possibly 0), such that no Complete String can be formed from the resulting string.
EXPLANATION:
We need to eliminate all the possibility of subsequences having consecutive occurrences of “c++”. This implies that there should not be more than one ‘+’ after any ‘c’; there should be zero occurrences of ‘c’ before any two '+'s. Hence what we can do is, for every ith position, we can delete all the 'c’s from 1^{st} to (i-1)^{th} position and all the '+'s (except 1) from the i^{th} to the last position in the string (only if there are more than one ‘+’). Then, take the minimum of all the positions.
There’s also a straightforward dp solution. If i consider the string “c++” (1-indexed,lets call this string t) then dp[i][j] means the minimum no. of letters of remove from the pos [i , n] in the given string (call it string s) so that it doesn’t contain any subsequence of the part of word “c++” from pos [j, 3].
Simple transitions:
if( t[j] == s[i] ) => dp[i][j] = min( 1 + dp[i+1][j] (if i choose to delete letter s[i]) , dp[i+1][j+1] (If i choose not to delete letter s[i] ) )
Otherwise
dp[i][j] = dp[i+1][j] (No need to delete the letter s[i]).
@wargang (in case it doesn’t reach you).
The required type of string is of the following format: \underbrace{++....+}_{\lt i}\underbrace{ccc...cc}_{\geq i}.
The section where the index is \geq i can also have at most one occurrence of +.
From here you can see that you’ll remove all occurences of c before i (@anshu23_1999 ) and all occurrences except one of + on and after i.