PROBLEM LINK
Author: Amit Pandey
Tester & Editorialist: Prateek Gupta
DIFFICULTY:
Medium Hard
PREREQUISITES:
Dynamic Programming, Strings
PROBLEM:
Given N strings each consisting of at-most 2 characters either of ‘a’ or ‘b’, delete the minimum number of strings such that rest of them can be concatenated to form a palindrome.
EXPLANATION
Solution for Subtask 1:
Since, the constraints for N are as small as 16, you can use bit masking to generate all possible combinations and find the one combination which after concatenation, needs minimum deletions to form a palindromic string. For each of the N strings, you have a choice either to take it or to not take it in the final formed string. Hence, each string can be assigned a bit 1 or 0 depending on whether it is chosen or not. Having said that, there will be 2^{N} such possible combinations. Let’s have a look at the pseudo code to gather a little more detail of what we are trying to accomplish.
ans = INFINITY
for ( mask = 0 to 2^n - 1 ) {
tmp = ""
deletions = 0
for ( i = 0 to n - 1 ) {
if ( bit i is set in mask ) tmp.append(s[j])
else deletions += 1
}
if ( tmp is palindrome ) ans = min(ans, deletions)
}
print(deletions)
The time complexity of the above approach will be {O}(N*2^{N})
Solution for subtask 2:
The best solution to the problem involves use of Dynamic Programming.
No matter, how much you are familiar with it! It doesn’t fail to surprise you, ain’t it!?
We can define the DP state as F(i,\ j,\ cnt1,\ cnt2) denoting the minimum number of strings to be removed in range(i,\ j) so that rest of the strings in the same range can be concatenated to form a palindrome, when cnt1 characters of i^{th} string and cnt2 characters of j^{th} string from the back, have matched already. Hence, value of the state F(0,\ N - 1,\ 0,\ 0) will give us the final result. At each state, there are a number of possibilities to consider. When you have already decided to take the i^{th} string in your final answer, you have no choice but to somehow match it from the j^{th} string where i\ <=\ j.
- Considering the base cases.
Let us have a look at the pseudo code for case i equals j.
if ( i == j ) {
sz = s[i].size()
idx1 = cnt1, idx2 = sz - cnt2 - 1
if ( idx1 > idx2 ) return INF
ans = INF
if ( cnt1 == 0 and cnt2 == 0 ) ans = 1 //you can always skip this ith string since you have not yet considered taking it.
while ( idx1 < idx2 ) {
if ( s[i][idx1] != s[i][idx2] ) return min(ans, INF)
idx1++, idx2--
}
return 0
}
- Considering the middle cases
Let us look at the pseudo code below to understand better.
ans = INF
//ignore the string at index i, since it's no characters have been matched yet
if ( cnt1 == 0 ) ans = min(ans, 1 + f(i + 1, j, 0, cnt2))
//ignore the string at index j, since it's no characters have been matched yet
if ( cnt2 == 0 ) ans = min(ans, 1 + f(i, j - 1, cnt1, 0))
sz1 = s[i].size()
sz2 = s[j].size()
//try to match string i with string j from back
if ( s[i][cnt1] == s[j][sz2-cnt2-1] ) {
//string i and string j not yet traversed fully.
if ( cnt1 + 1 < sz1 && cnt2 + 1 < sz2 ) ans = min(ans, f(i, j, cnt1 + 1, cnt2 + 1))
//string i not yet traversed fully, but j traversed.
else if ( cnt1 + 1 < sz1 ) ans = min(ans, f(i, j - 1, cnt1 + 1, 0))
//string i traversed fully, but j not yet traversed completely.
else if ( cnt2 + 1 < sz2 ) ans = min(ans, f(i + 1, j, 0, cnt2 + 1))
//both string i and string j traversed completely.
else ans = min(ans, f(i + 1, j - 1, 0, 0))
}
return ans
For details on the implementation of any subtasks, have a look at the tester’s solutions. If you wish to read more about Dynamic Programming, you might like to go through this blog post.
COMPLEXITY
Overall time and space complexity for the solution remains \mathcal{O}(N^{2})
SOLUTIONS
Tester’s solution to Subtask 1
Tester’s solution to Subtask 2