Get all palindromes

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.

Advertisement