Palindrome Partitioning Problem in Java

15 Nov 2025 | 8 min read

The palindrome partitioning of a string means dividing the given string in such a way that each substring formed from the given string is a palindrome in itself. In the palindrome partitioning problem in Java, we return the minimum of cuts required to make each of the substrings of the given string palindrome. Let's understand with the help of a few examples.

Example 1:

String str = "pmptuiutpmp"

Minimum number of cuts = 0

It is because the given string is a palindrome. Hence, no cut is required.

Example 2:

String str = "pmpmmmpmmpmpmp"

Minimum number of cuts = 3

With the 3 cuts, we can split the given string into 4 substrings such that each substring is a palindrome. Those 3 cuts are mentioned below.

pmp | m | mmpmm | pmpmp

We see that substrings "pmp", "m", "mmpmm", and "pmpmp" are palindrome.

Example 3:

String str = "pqrstu"

Minimum number of cuts = 5

With the 5 cuts, we can split the given string into 6 substrings such that each substring is a palindrome. Those 5 cuts are mentioned below.

p | q | r | s | t | u

We see that substrings "p", "q", "r", "s", "t", and "u" are palindrome.

There are mainly two approaches to solve this problem: one is the recursive approach, and the other is the iterative approach. Let's start with the recursive approach first.

Using Recursion

Let's see the implementation of the recursive approach.

FileName: PalinPartition.java

Output:

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

Using Iteration

Let's see the implementation of the iterative approach.

FileName: PalinPartition1.java

Output:

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

In the above approach, we are finding the solution using the for loops nested to a level of degree 3. Hence, the above approach is time-consuming. Therefore, the above-mentioned solution will be rejected by the interviewer most number of times, or the interviewer can ask to optimize the solution. The optimization of the above solution is mentioned below.

FileName: PalinPartition2.java

Output:

For the string 'pmpmmmpmmpmpmp' the number of minimum cuts is: 3
For the string 'pqrstu' the number of minimum cuts is: 5
For the string 'pmptuiutpmp' the number of minimum cuts is: 0

The solution that is provided above never uses the nesting of the for-loop to the 3rd level. Only two-level nesting of for-loop is used. Thus, it consumes less time to find the solution as compared to the last discussed approach. Hence, the above approach is better than the last discussed approach.

Next TopicDifference-between-concurrenthashmap-hashtable-and-synchronized-map-in-java

← prev next →