Problem Link:Author and Editorialist Vineet Paliwal 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,b1) otherwise false . Note : Please take care of boundary conditions while using recursive formula for isPalindrome and dp. Solutions:
This question is marked "community wiki".
asked 27 Oct '13, 14:21

O(n^3) solution is getting 100/100 (passing even the subtask3). 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
as discussed above remains as it is in my code. answered 29 Oct '13, 08:29

My n^2 solution is also showing tle http://www.codechef.com/LTIME05/problems/CHGLSTGT answered 29 Oct '13, 21:30

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

can someone please tell me whats wrong in my code
http://ideone.com/Pn3fpM