CHGLSTGT - Editorial

Problem Link:

Practice
Contest

Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko

Difficulty:

Simple

PREREQUISITES :

Dynamic Programming , Strings , Palindromes

PROBLEM :

Given a string , what is the minimum number of substrings in which you can break the given string so that each substring is a palindrome .

EXPLANATION:

The Naive Solution :

Consider all possible ways of breaking the string into substrings . This number of ways will be exponential and hence only one subtask can be solved using this .

Using Dynamic Programming :

Let dp[i] denote the minimum number of partitions for breaking the the first i characters of the string into palindromes .

Then for a given i , dp[i] = min of dp[j] + 1 ( if string[j+1 … i] is a palindrome , j belongs to { 0 … i }) .

This gives an O(n^3) solution .

However we can precompute whether string[a…b] is a palindrome or not by dynamic programming again reducing the overall complexity to O(n^2) .

isPalindrome(a,b) = true if string[a] = string[b] and isPalindrome(a+1,b-1) otherwise false .

Note : Please take care of boundary conditions while using recursive formula for isPalindrome and dp.

Solutions:

Setter’s Solution
Tester’s Solution

4 Likes

O(n^3) solution is getting 100/100 (passing even the subtask-3).

http://www.codechef.com/viewsolution/2895171

I have not used dp to check if substring(i,j) is a palindrome or not. I have simply iterated over the (i,j) substring from right as well as left simultaneously and compared the ith and jth char.

NOTE that the main approach of

dp[i] = min of dp[j] + 1 ( if string[j+1 ... i] is a palindrome , j belongs to { 0 .. i })

as discussed above remains as it is in my code.

My n^2 solution is also showing tle http://www.codechef.com/LTIME05/problems/CHGLSTGT

We can also generate all Palindromes (i,j+1) { where s[i…j] is palindrome and j+1 is next index } as a Graph in O(n^2), and perform BFS(0) till we get N.
Link to my Solution.

can someone please tell me whats wrong in my code

Don’t know why WA. My WA code.
It would be great if anyone could help.