# Problem Link:

**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.