You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 27 Oct '13, 14:21

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

edited 16 Jun '15, 11:39

vicky002's gravatar image

1★vicky002 ♦♦
2561314

can someone please tell me whats wrong in my code

http://ideone.com/Pn3fpM

(28 Oct '13, 20:44) sanjeevmsk1★

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.

link

answered 29 Oct '13, 08:29

shobhit6993's gravatar image

3★shobhit6993
4954410
accept rate: 0%

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

link

answered 29 Oct '13, 21:30

varuntinkle's gravatar image

3★varuntinkle
11431012
accept rate: 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.

link

answered 02 Dec '16, 20:08

rsampaths16's gravatar image

5★rsampaths16
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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