×

# AHWORK - Editorial

Author: Amit Pandey
Tester & Editorialist: Prateek Gupta

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

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})$

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.
• $$F(i,\ j,\ cnt1,\ cnt2)\ =\ 0,\ \forall\ i\ >\ j,\ cnt1\ =\ 0\ and\ cnt2\ =\ 0$$ $$F(i,\ j,\ cnt1,\ cnt2)\ =\ INF,\ \forall\ i\ >\ j,\ cnt1\ !=\ 0\ or\ cnt2\ !=\ 0$$

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

20421223
accept rate: 0%

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! :-/

(28 May '16, 22:40)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,679
×2,169
×349
×126

question asked: 19 May '16, 12:49

question was seen: 2,068 times

last updated: 29 May '16, 11:41