×

# CHGLSTGT - Editorial

Author and Editorialist Vineet Paliwal
Tester Roman Rubanenko

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:

This question is marked "community wiki".

12.4k47107171
accept rate: 12%

2561314

can someone please tell me whats wrong in my code

http://ideone.com/Pn3fpM

(28 Oct '13, 20:44)

 0 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. answered 29 Oct '13, 08:29 495●4●4●10 accept rate: 0%
 0 My n^2 solution is also showing tle http://www.codechef.com/LTIME05/problems/CHGLSTGT answered 29 Oct '13, 21:30 114●3●10●12 accept rate: 0%
 0 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. answered 02 Dec '16, 20:08 11 accept rate: 0%
 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,852
×1,191
×966
×354
×157
×36
×8

question asked: 27 Oct '13, 14:21

question was seen: 4,025 times

last updated: 02 Dec '16, 20:08