CHGLSTGT - Editorial

editorial
, , , , , ,
1

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

3 Likes
2

can someone please tell me whats wrong in my code

3

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.

4

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

5

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.