# PROBLEM LINK

Practice

Contest

**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$.

```
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

I made the exact same state of dp in my code along with all the cases taken care of.. Don't know why it got WA! :-/