Problem Definition:
given a string of length n check for all subsets of this string if the are
palindromes or not.
Problem Tackling Approach:
To solve this problem in a brute force way it will take about O(n^3) ,because it
will be something like this.
Algorithm 1:
For all char ‘a’ belongs to S do
For all char ‘b’ belongs S and after char ‘a’ do
Check_Palindrome(String(a,b))
This algorithm is doomed if it’s part in solving a bigger problem also if n grows large, but this algorithm showed a pattern here let’s look at this example.
Ex1:
Let our string here be “aaabbaaa”, when we apply Algorithm 1 you will notice the pattern when we apply function “Check_Palindromes” first to the string starting at index 0 to index 7 and to string at index 1 to index 6.
The Pattern is we checked if the substring from index 2 to 5 is palindrome twice!.
This pattern tells us we can divide it into small subsets and solve it with straight forward Dynammic Programming with O(n^2).
Algorithm 2:
for ( int spaces = 1; spaces < n; spaces++)
for(int startIndex = 0; startIndex < n && startIndex+spaces < n; startIndex++)
If( String[startIndex] == String[startIndex + spaces] && DP[startIndex+1][spaces-1])
{
DP[startIndex][spaces] = true;
}
Ok, that’s all of it hope you find it challenging.
Problem Reference:
-idea of the problem taken from codechef Octobor 2010 contest.
Hey, I remembered I have solved the same problem on CodeChef October 2010 Contest. And yes, the problem was an interesting DP 🙂
Yes it was a nice one :D.