Palindrome Partitioning

Last Updated : 07 Nov, 2024

Try it on GfG Practice

Given a string s, the task is to find the minimum number of cuts needed for palindrome partitioning of the given string. A partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome.

Examples:

Input: s = “geek”
Output: 2
Explanation: We need to make minimum 2 cuts, i.e., “g | ee | k”.

Input: s= “aaaa”
Output: 0
Explanation: The string is already a palindrome.

Input: s = “ababbbabbababa”
Output: 3
Explanation: We need to make minimum 3 cuts, i.e., “aba | bb | babbab | aba”.

Table of Content

Using Recursion – O(n * 2^n) Time and O(n) Space
Using Top-Down DP (Memoization) – O(n^3) Time and O(n^2) Space
Using Bottom-Up DP (Tabulation) – O(n^3) Time and O(n^2) Space
Using Optimised Bottom-Up DP (Tabulation) – O(n^2) Time and O(n^2) Space

Using Recursion – O(n * 2^n) Time and O(n) Space

In this approach, we will try to apply all possible partitions and at the end return the correct combination of partitions.

This approach is similar to that of Matrix Chain Multiplication problem.

In this approach, we recursively evaluate the following conditions:

Base Case: If the current string is a palindrome, then we simply return 0, no Partitioning is required.
Else, like the Matrix Chain Multiplication problem,
we try making cuts at all possible places,
recursively calculate the cost for each cut
return the minimum value.

C++

// C++ Program for Palindrome Partitioning Problem
// using Recursion
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

// Function to Check if a substring is a palindrome
bool isPalindrome(string& s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
    return true;
}

// Recursive Function to find the minimum number of 
// cuts needed for palindrome partitioning
int palPartitionRec(string& s, int i, int j) {
  
    // Base case: If the substring is empty or 
      // a palindrome, no cuts needed
    if (i >= j || isPalindrome(s, i, j))
        return 0;

    int res = INT_MAX, cuts;

    // Iterate through all possible partitions and 
      // find the minimum cuts needed
    for (int k = i; k < j; k++) {
        cuts = 1 + palPartitionRec(s, i, k)
                    + palPartitionRec(s, k + 1, j);
        res = min(res, cuts);
    }

    return res;
}

int palPartition(string &s) {
      return palPartitionRec(s, 0, s.size()-1);
}

int main() {
    string s = "ababbbabbababa";

    cout << palPartition(s) << endl;
    return 0;
}

C

// C Program for Palindrome Partitioning Problem
// using Recursion
#include <stdio.h>
#include <string.h>
#include <limits.h>

// Function to check if a substring is a palindrome
int isPalindrome(char* s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j])
            return 0;
        i++;
        j--;
    }
    return 1;
}

// Recursive function to find the minimum number 
// of cuts needed for palindrome partitioning
int palPartitionRec(char* s, int i, int j) {
  
    // Base case: If the substring is empty 
      // or a palindrome, no cuts needed
    if (i >= j || isPalindrome(s, i, j))
        return 0;

    int res = INT_MAX, cuts;

    // Iterate through all possible partitions 
      // and find the minimum cuts needed
    for (int k = i; k < j; k++) {
        cuts = 1 + palPartitionRec(s, i, k) + palPartitionRec(s, k + 1, j);
        if (cuts < res) res = cuts;
    }

    return res;
}

int palPartition(char* s) {
    return palPartitionRec(s, 0, strlen(s) - 1);
}

int main() {
    char s[] = "ababbbabbababa";
    printf("%d\n", palPartition(s));
    return 0;
}

Java

// Java Program for Palindrome Partitioning Problem
// using Recursion
import java.util.*;

class GfG {

    // Function to check if a substring is a palindrome
    static boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }

    // Recursive function to find the minimum number of 
      // cuts needed for palindrome partitioning
    static int palPartitionRec(String s, int i, int j) {
      
        // Base case: If the substring is empty
          // or a palindrome, no cuts needed
        if (i >= j || isPalindrome(s, i, j))
            return 0;

        int res = Integer.MAX_VALUE, cuts;

        // Iterate through all possible partitions 
          // and find the minimum cuts needed
        for (int k = i; k < j; k++) {
            cuts = 1 + palPartitionRec(s, i, k) + 
                          palPartitionRec(s, k + 1, j);
            res = Math.min(res, cuts);
        }

        return res;
    }

    static int palPartition(String s) {
        return palPartitionRec(s, 0, s.length() - 1);
    }

    public static void main(String[] args) {
        String s = "ababbbabbababa";
        System.out.println(palPartition(s));
    }
}

Python

# Python Program for Palindrome Partitioning Problem
# using Recursion
import sys

# Function to check if a substring is a palindrome
def isPalindrome(s, i, j):
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

# Recursive function to find the minimum number 
# of cuts needed for palindrome partitioning
def palPartitionRec(s, i, j):
  
    # Base case: If the substring is empty 
    # or a palindrome, no cuts needed
    if i >= j or isPalindrome(s, i, j):
        return 0

    res = sys.maxsize

    # Iterate through all possible partitions 
    # and find the minimum cuts needed
    for k in range(i, j):
        cuts = 1 + palPartitionRec(s, i, k) \
                 + palPartitionRec(s, k + 1, j)
        res = min(res, cuts)

    return res

def palPartition(s):
    return palPartitionRec(s, 0, len(s) - 1)

if __name__ == "__main__":
    s = "ababbbabbababa"
    print(palPartition(s))

C#

// C# Program for Palindrome Partitioning Problem
// using Recursion
using System;

class GfG {

    // Function to check if a substring is a palindrome
    static bool isPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    // Recursive function to find the minimum number of 
      // cuts needed for palindrome partitioning
    static int palPartitionRec(string s, int i, int j) {
      
        // Base case: If the substring is empty 
          // or a palindrome, no cuts needed
        if (i >= j || isPalindrome(s, i, j))
            return 0;

        int res = int.MaxValue, cuts;

        // Iterate through all possible partitions 
          // and find the minimum cuts needed
        for (int k = i; k < j; k++) {
            cuts = 1 + palPartitionRec(s, i, k) 
                          + palPartitionRec(s, k + 1, j);
            res = Math.Min(res, cuts);
        }

        return res;
    }

    static int palPartition(string s) {
        return palPartitionRec(s, 0, s.Length - 1);
    }

    static void Main() {
        string s = "ababbbabbababa";
        Console.WriteLine(palPartition(s));
    }
}

JavaScript

// JavaScript Program for Palindrome Partitioning Problem
// using Recursion

// Function to check if a substring is a palindrome
function isPalindrome(s, i, j) {
    while (i < j) {
        if (s[i] !== s[j])
            return false;
        i++;
        j--;
    }
    return true;
}

// Recursive function to find the minimum number 
// of cuts needed for palindrome partitioning
function palPartitionRec(s, i, j) {

    // Base case: If the substring is empty 
    // or a palindrome, no cuts needed
    if (i >= j || isPalindrome(s, i, j))
        return 0;

    let res = Number.MAX_SAFE_INTEGER, cuts;

    // Iterate through all possible partitions 
    // and find the minimum cuts needed
    for (let k = i; k < j; k++) {
        cuts = 1 + palPartitionRec(s, i, k) 
                    + palPartitionRec(s, k + 1, j);
        res = Math.min(res, cuts);
    }

    return res;
}

function palPartition(s) {
    return palPartitionRec(s, 0, s.length - 1);
}

const s = "ababbbabbababa";
console.log(palPartition(s));

Output

Using Top-Down DP (Memoization) – O(n^3) Time and O(n^2) Space

The above recursive approach has overlapping subproblems, leading to redundant computations thereby resulting in exponential time complexity. This redundant computation can be solved by using Memoization.

To avoid redundant computations, we can memoize results of each subproblem and reuse them as needed. A 2D array can serve as a memoization table to store solutions for overlapping subproblems. The size of this memo table will be n*n, as there are n possible starting indices and n possible ending indices for any subarray.

C++

// C++ Program for Palindrome Partitioning Problem
// Using Top-Down DP
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

// Function to Check if a substring is a palindrome
bool isPalindrome(string& s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j])
            return false;
        i++;
        j--;
    }
    return true;
}

// Recursive Function to find the minimum number of 
// cuts needed for palindrome partitioning
int palPartitionRec(string& s, int i, int j, 
                        vector<vector<int>>& memo) {
      
      // check in memo for 
      if (memo[i][j] != -1) 
          return memo[i][j];
  
    // Base case: If the substring is empty or 
      // a palindrome, no cuts needed
    if (i >= j || isPalindrome(s, i, j))
        return memo[i][j] = 0;

    int res = INT_MAX, cuts;

    // Iterate through all possible partitions and 
      // find the minimum cuts needed
    for (int k = i; k < j; k++) {
        cuts = 1 + palPartitionRec(s, i, k, memo)
                + palPartitionRec(s, k + 1, j, memo);
        res = min(res, cuts);
    }

    return memo[i][j] = res;
}

int palPartition(string &s) {
      int n = s.size();
  
      // declare a memo array to store the result
      // and initialise it with -1
      vector<vector<int>> memo(n, vector<int> (n, -1));
  
      return palPartitionRec(s, 0, n - 1, memo);
}

int main() {
    string s = "ababbbabbababa";

    cout << palPartition(s) << endl;
    return 0;
}

Java

// Java Program for Palindrome Partitioning Problem
// Using Top-Down DP
import java.util.Arrays;

class GfG {

    // Function to check if a substring is a palindrome
    static boolean isPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) 
                return false;
            i++;
            j--;
        }
        return true;
    }

    // Recursive function to find the minimum number of 
      // cuts needed for palindrome partitioning
    static int palPartitionRec(String s, int i, int j, int[][] memo) {
      
        // check in memo for previously computed results
        if (memo[i][j] != -1) 
            return memo[i][j];

        // Base case: If the substring is empty or 
          // a palindrome, no cuts needed
        if (i >= j || isPalindrome(s, i, j)) 
            return memo[i][j] = 0;

        int res = Integer.MAX_VALUE, cuts;

        // Iterate through all possible partitions and
          // find the minimum cuts needed
        for (int k = i; k < j; k++) {
            cuts = 1 + palPartitionRec(s, i, k, memo) 
                       + palPartitionRec(s, k + 1, j, memo);
            res = Math.min(res, cuts);
        }

        return memo[i][j] = res;
    }

    static int palPartition(String s) {
        int n = s.length();
        int[][] memo = new int[n][n];
        
        // Initialize memo array with -1
        for (int[] row : memo)
            Arrays.fill(row, -1);
        
        return palPartitionRec(s, 0, n - 1, memo);
    }

    public static void main(String[] args) {
        String s = "ababbbabbababa";
        System.out.println(palPartition(s));
    }
}

Python

# Python Program for Palindrome Partitioning Problem
# Using Top-Down DP
import sys

# Function to check if a substring is a palindrome
def isPalindrome(s, i, j):
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

# Recursive function to find the minimum number of
# cuts needed for palindrome partitioning
def palPartitionRec(s, i, j, memo):
  
    # Check memo for previously computed results
    if memo[i][j] != -1:
        return memo[i][j]

    # Base case: If the substring is empty or 
    # a palindrome, no cuts needed
    if i >= j or isPalindrome(s, i, j):
        memo[i][j] = 0
        return 0

    res = sys.maxsize

    # Iterate through all possible partitions and
    # find the minimum cuts needed
    for k in range(i, j):
        cuts = 1 + palPartitionRec(s, i, k, memo) \
        + palPartitionRec(s, k + 1, j, memo)
        res = min(res, cuts)

    memo[i][j] = res
    return res

def palPartition(s):
    n = len(s)
    memo = [[-1 for _ in range(n)] for _ in range(n)]
    return palPartitionRec(s, 0, n - 1, memo)

if __name__ == "__main__":
    s = "ababbbabbababa"
    print(palPartition(s))

C#

// C# Program for Palindrome Partitioning Problem
// Using Top-Down DP
using System;

class GfG {

    // Function to check if a substring is a palindrome
    static bool isPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) 
                return false;
            i++;
            j--;
        }
        return true;
    }

    // Recursive function to find the minimum number of 
      // cuts needed for palindrome partitioning
  
    static int palPartitionRec(string s, int i, 
                                   int j, int[,] memo) {
      
        // Check memo for previously computed results
        if (memo[i, j] != -1) 
            return memo[i, j];

        // Base case: If the substring is empty 
          // or a palindrome, no cuts needed
        if (i >= j || isPalindrome(s, i, j)) 
            return memo[i, j] = 0;

        int res = int.MaxValue, cuts;

        // Iterate through all possible partitions 
          // and find the minimum cuts needed
        for (int k = i; k < j; k++) {
            cuts = 1 + palPartitionRec(s, i, k, memo) 
                  + palPartitionRec(s, k + 1, j, memo);
            res = Math.Min(res, cuts);
        }

        return memo[i, j] = res;
    }

    static int palPartition(string s) {
        int n = s.Length;
        int[,] memo = new int[n, n];

        // Initialize memo array with -1
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                memo[i, j] = -1;

        return palPartitionRec(s, 0, n - 1, memo);
    }

    static void Main() {
        string s = "ababbbabbababa";
        Console.WriteLine(palPartition(s));
    }
}

JavaScript

// JavaScript Program for Palindrome Partitioning Problem
// Using Top-Down DP

// Function to check if a substring is a palindrome
function isPalindrome(s, i, j) {
    while (i < j) {
        if (s[i] !== s[j])
            return false;
        i++;
        j--;
    }
    return true;
}

// Recursive function to find the minimum number of 
// cuts needed for palindrome partitioning
function palPartitionRec(s, i, j, memo) {

    // Check memo for previously computed results
    if (memo[i][j] !== -1) 
        return memo[i][j];

    // Base case: If the substring is empty or 
    // a palindrome, no cuts needed
    if (i >= j || isPalindrome(s, i, j))
        return memo[i][j] = 0;

    let res = Infinity, cuts;

    // Iterate through all possible partitions 
    // and find the minimum cuts needed
    for (let k = i; k < j; k++) {
        cuts = 1 + palPartitionRec(s, i, k, memo) 
                + palPartitionRec(s, k + 1, j, memo);
        res = Math.min(res, cuts);
    }

    return memo[i][j] = res;
}

function palPartition(s) {
    const n = s.length;
    const memo = Array.from({ length: n }, 
                    () => Array(n).fill(-1));
    return palPartitionRec(s, 0, n - 1, memo);
}

const s = "ababbbabbababa";
console.log(palPartition(s));

Output

Using Bottom-Up DP (Tabulation) – O(n^3) Time and O(n^2) Space

The approach is similar to the previous one; just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner.

Here, we can use two 2D array dp[][] and isPalin[][], for storing the computed result.

dp[i][j] stores the minimum cuts for palindrome partitioning of the substring s[i … j]
isPalin[i][j] tells us whether substring s[i … j] is a palindromic string or not.
We starts with smaller substrings and gradually builds up to the result for entire string.

C++

// C++ Solution for Palindrome Partitioning Problem
// using Bottom Up Dynamic Programming
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to find the minimum number of cuts 
// needed to partition a string such that 
// every part is a palindrome
int palPartition(string& s) {
    int n = s.length();

    // dp[i][j] = Minimum number of cuts needed for
    // palindrome partitioning of substring s[i..j]
    int dp[n][n];

    // isPalin[i][j] = true if substring s[i..j] 
      // is palindrome,else false
    bool isPalin[n][n];

    // Every substring of length 1 is a palindrome
    for (int i = 0; i < n; i++) {
        isPalin[i][i] = true;
        dp[i][i] = 0;
    }

    for (int len = 2; len <= n; len++) {

        // Build solution for all substrings s[i ... j] 
          // of length len
        for (int i = 0, j = i + len - 1; j < n ; i++, j++) {
          
            // If len is 2, then we just need to
            // compare two characters. 
            if (len == 2)
                isPalin[i][j] = (s[i] == s[j]);
          
              // Else need to check two corner characters
            // and value of isPalin[i+1][j-1]
            else
                isPalin[i][j] = (s[i] == s[j]) && 
                                      isPalin[i + 1][j - 1];

            // IF s[i..j] is palindrome, then dp[i][j] is 0
            if (isPalin[i][j] == true)
                dp[i][j] = 0;
            else {

            // Make a cut at every possible location starting 
              // from i to j, and get the minimum cost cut.
                dp[i][j] = INT_MAX;
                for (int k = i; k <= j - 1; k++)
                    dp[i][j] = min(dp[i][j], 1 + 
                                   dp[i][k] + dp[k + 1][j]);
            }
        }
    }

    // Return the min cut value for
    // complete string. i.e., s[0..n-1]
    return dp[0][n - 1];
}

int main() {
    string s = "ababbbabbababa";

    cout << palPartition(s) << endl;
    return 0;
}

Java

// Java Solution for Palindrome Partitioning Problem
// using Bottom Up Dynamic Programming
import java.util.Arrays;

class GfG {

    // Function to find the minimum number of cuts 
    // needed to partition a string such that 
    // every part is a palindrome
    static int palPartition(String s) {
        int n = s.length();

        // dp[i][j] = Minimum number of cuts needed for
        // palindrome partitioning of substring s[i..j]
        int[][] dp = new int[n][n];

        // isPalin[i][j] = true if substring s[i..j] 
        // is palindrome, else false
        boolean[][] isPalin = new boolean[n][n];

        // Every substring of length 1 is a palindrome
        for (int i = 0; i < n; i++) {
            isPalin[i][i] = true;
            dp[i][i] = 0;
        }

        for (int len = 2; len <= n; len++) {

            // Build solution for all  substrings s[i ... j] 
            // of length len
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {

                // If len is 2, then we just need to
                // compare two characters.
                if (len == 2)
                    isPalin[i][j] = (s.charAt(i) == s.charAt(j));

                // Else need to check two corner characters
                // and value of isPalin[i+1][j-1]
                else
                    isPalin[i][j] = (s.charAt(i) == s.charAt(j)) 
                                          && isPalin[i + 1][j - 1];

                // IF s[i..j] is palindrome, then dp[i][j] is 0
                if (isPalin[i][j])
                    dp[i][j] = 0;
                else {

                    // Make a cut at every possible location starting 
                    // from i to j, and get the minimum cost cut.
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k <= j - 1; k++)
                        dp[i][j] = Math.min(dp[i][j], 1 + 
                                          dp[i][k] + dp[k + 1][j]);
                }
            }
        }

        // Return the min cut value for
        // complete string. i.e., s[0..n-1]
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        String s = "ababbbabbababa";
        System.out.println(palPartition(s));
    }
}

Python

# Python Solution for Palindrome Partitioning Problem
# using Bottom Up Dynamic Programming

# Function to find the minimum number of cuts 
# needed to partition a string such that 
# every part is a palindrome
def palPartition(s):
    n = len(s)

    # dp[i][j] = Minimum number of cuts needed for
    # palindrome partitioning of substring s[i..j]
    dp = [[0] * n for _ in range(n)]

    # isPalin[i][j] = true if substring s[i..j] 
    # is palindrome, else false
    isPalin = [[False] * n for _ in range(n)]

    # Every substring of length 1 is a palindrome
    for i in range(n):
        isPalin[i][i] = True
        dp[i][i] = 0

    for length in range(2, n + 1):

        # Build solution for all  substrings s[i ... j] 
        # of length len
        for i in range(n - length + 1):
            j = i + length - 1

            # If len is 2, then we just need to
            # compare two characters.
            if length == 2:
                isPalin[i][j] = (s[i] == s[j])
                
            # Else need to check two corner characters
            # and value of isPalin[i+1][j-1]
            else:
                isPalin[i][j] = (s[i] == s[j]) and isPalin[i + 1][j - 1]

            # IF s[i..j] is palindrome, then dp[i][j] is 0
            if isPalin[i][j]:
                dp[i][j] = 0
            else:
                # Make a cut at every possible location starting 
                # from i to j, and get the minimum cost cut.
                dp[i][j] = min(1 + dp[i][k] + dp[k + 1][j] for k in range(i, j))

    # Return the min cut value for
    # complete string. i.e., s[0..n-1]
    return dp[0][n - 1]

if __name__ == "__main__":
    s = "ababbbabbababa"
    print(palPartition(s))

C#

// C# Solution for Palindrome Partitioning Problem
// using Bottom Up Dynamic Programming
using System;

class GfG {

    // Function to find the minimum number of cuts 
    // needed to partition a string such that 
    // every part is a palindrome
    static int palPartition(string s) {
        int n = s.Length;

        // dp[i][j] = Minimum number of cuts needed for
        // palindrome partitioning of substring s[i..j]
        int[,] dp = new int[n, n];

        // isPalin[i][j] = true if substring s[i..j] 
        // is palindrome, else false
        bool[,] isPalin = new bool[n, n];

        // Every substring of length 1 is a palindrome
        for (int i = 0; i < n; i++) {
            isPalin[i, i] = true;
            dp[i, i] = 0;
        }

        for (int len = 2; len <= n; len++) {

            // Build solution for all substrings s[i ... j] 
            // of length len
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {

                // If len is 2, then we just need to
                // compare two characters.
                if (len == 2)
                    isPalin[i, j] = (s[i] == s[j]);

                // Else need to check two corner characters
                // and value of isPalin[i+1][j-1]
                else
                    isPalin[i, j] = (s[i] == s[j]) && 
                                          isPalin[i + 1, j - 1];

                // IF s[i..j] is palindrome, then dp[i][j] is 0
                if (isPalin[i, j])
                    dp[i, j] = 0;
                else {

                    // Make a cut at every possible location starting 
                    // from i to j, and get the minimum cost cut.
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k <= j - 1; k++)
                        dp[i, j] = Math.Min(dp[i, j], 1 + 
                                            dp[i, k] + dp[k + 1, j]);
                }
            }
        }

        // Return the min cut value for
        // complete string. i.e., s[0..n-1]
        return dp[0, n - 1];
    }

    static void Main() {
        string s = "ababbbabbababa";
        Console.WriteLine(palPartition(s));
    }
}

JavaScript

// JavaScript Solution for Palindrome Partitioning Problem
// using Bottom Up Dynamic Programming

// Function to find the minimum number of cuts 
// needed to partition a string such that 
// every part is a palindrome
function palPartition(s) {
    let n = s.length;

    // dp[i][j] = Minimum number of cuts needed for
    // palindrome partitioning of substring s[i..j]
    let dp = Array.from({ length: n }, 
                                () => Array(n).fill(0));

    // isPalin[i][j] = true if substring s[i..j] 
    // is palindrome, else false
    let isPalin = Array.from({ length: n }, 
                            () => Array(n).fill(false));

    // Every substring of length 1 is a palindrome
    for (let i = 0; i < n; i++) {
        isPalin[i][i] = true;
        dp[i][i] = 0;
    }

    for (let len = 2; len <= n; len++) {

        // Build solution for all substrings s[i ... j] 
        // of length len
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1;

            // If len is 2, then we just need to
            // compare two characters.
            if (len === 2)
                isPalin[i][j] = (s[i] === s[j]);

            // Else need to check two corner characters
            // and value of isPalin[i+1][j-1]
            else
                isPalin[i][j] = (s[i] === s[j]) && 
                                    isPalin[i + 1][j - 1];

            // IF s[i..j] is palindrome, then dp[i][j] is 0
            if (isPalin[i][j])
                dp[i][j] = 0;
            else {

                // Make a cut at every possible location starting 
                // from i to j, and get the minimum cost cut.
                dp[i][j] = Infinity;
                for (let k = i; k <= j - 1; k++)
                    dp[i][j] = Math.min(dp[i][j], 1 + 
                            dp[i][k] + dp[k + 1][j]);
            }
        }
    }

    // Return the min cut value for
    // complete string. i.e., s[0..n-1]
    return dp[0][n - 1];
}

let s = "ababbbabbababa";
console.log(palPartition(s));

Output

Using Optimised Bottom-Up DP (Tabulation) – O(n^2) Time and O(n^2) Space

The problem can be solved by finding the suffix starting from j and ending at index i, (1 <= j <= i <= n – 1), which are palindromes. Hence, we can make a cut here that requires 1 + min cut from rest substring [0, j – 1]. For all such palindromic suffixes starting at j and ending at i, keep minimising in dp[i]. Similarly, we need to compute results for all such i. (1 <= i <= n – 1) and finally, dp[n – 1] will be the minimum number of cuts needed for palindrome partitioning of the given string.

C++

// C++ Solution for Palindrome Partitioning Problem
// using Optimised Bottom Up Dynamic Programming
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to fill isPalin array such that isPalin[i][j] 
// stores whether substring s[i, j] is a palindrome or not
void generatePal(string& s, vector<vector<bool>>& isPalin) {
    int n = s.size();

    // Substring s[i .. i] of len 1 
      // is always palindromic
    for (int i = 0; i < n; i++) {
        isPalin[i][i] = true;
    }

    // Iterate over different lengths of substrings
    for (int len = 2; len <= n; len++) {
      
        for (int i = 0, j = i + len - 1; j < n ; i++, j++) {
          
            // Check whether s[i] == s[j] and the
            // substring between them is a palindrome
            if (s[i] == s[j] && (len == 2 
                                 || isPalin[i + 1][j - 1])) {

                // Mark the substring from i to j as a
                // palindrome
                isPalin[i][j] = true;
            }
        }
    }
}

// Function to calculate the minimum number of cuts required
// to make all substrings of 's' palindromic
int palPartition(string& s) {
    int n = s.size();

    // 2D array to store whether substring 
      // s[i, j] is a palindrome or not
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));

    generatePal(s, isPalin);

    // dp[i] stores minimum cuts for Palindrome 
      // Partitioning of substring s[0...i] 
    vector<int> dp(n, n);

    // There is no cut required for single character
    // as it is always palindrome
    dp[0] = 0;

    // Iterate over the given string
    for (int i = 1; i < n; i++) {

        // Check if string 0 to i is palindrome.
        if (isPalin[0][i]) {
          
              // if palindrome then cuts required is 0
            dp[i] = 0;
        }
        else {
            for (int j = i; j >= 1; j--) {
              
                  // if substring s[j...i] is palindromic
                  // then we can make a cut over here
                if (isPalin[j][i]) {

                      // update dp[i] with minimum cuts
                      dp[i] = min(dp[i], 1 + dp[j-1]);
                }
            }
        }
    }

    // Return the minimum cuts required 
      // for the entire string 's'
    return dp[n - 1];
}

int main() {
    string s = "ababbbabbababa";

    cout << palPartition(s) << endl;
    return 0;
}

Java

// Java Solution for Palindrome Partitioning Problem
// using Optimised Bottom Up Dynamic Programming
import java.util.Arrays;

class GfG {

    // Function to fill isPalin array such that isPalin[i][j] 
    // stores whether substring s[i, j] is a palindrome or not
    static void generatePal(String s, boolean[][] isPalin) {
        int n = s.length();

        // Substring s[i .. i] of len 1 
        // is always palindromic
        for (int i = 0; i < n; i++) {
            isPalin[i][i] = true;
        }

        // Iterate over different lengths of substrings
        for (int len = 2; len <= n; len++) {
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {

                // Check whether s[i] == s[j] and the
                // substring between them is a palindrome
                if (s.charAt(i) == s.charAt(j) && 
                    (len == 2 || isPalin[i + 1][j - 1])) {

                    // Mark the substring from i to j as a
                    // palindrome
                    isPalin[i][j] = true;
                }
            }
        }
    }

    // Function to calculate the minimum number of cuts required
    // to make all substrings of 's' palindromic
    static int palPartition(String s) {
        int n = s.length();

        // 2D array to store whether substring 
        // s[i, j] is a palindrome or not
        boolean[][] isPalin = new boolean[n][n];

        generatePal(s, isPalin);

        // dp[i] stores minimum cuts for Palindrome 
        // Partitioning of substring s[0...i] 
        int[] dp = new int[n];
        Arrays.fill(dp, n);

        // There is no cut required for single character
        // as it is always palindrome
        dp[0] = 0;

        // Iterate over the given string
        for (int i = 1; i < n; i++) {

            // Check if string 0 to i is palindrome.
            if (isPalin[0][i]) {

                // if palindrome then cuts required is 0
                dp[i] = 0;
            } else {
                for (int j = i; j >= 1; j--) {

                    // if substring s[j...i] is palindromic
                    // then we can make a cut over here
                    if (isPalin[j][i]) {

                        // update dp[i] with minimum cuts
                        dp[i] = Math.min(dp[i], 1 + dp[j - 1]);
                    }
                }
            }
        }

        // Return the minimum cuts required 
        // for the entire string 's'
        return dp[n - 1];
    }

    public static void main(String[] args) {
        String s = "ababbbabbababa";
        System.out.println(palPartition(s));
    }
}

Python

# Python Solution for Palindrome Partitioning Problem
# using Optimised Bottom Up Dynamic Programming

# Function to fill isPalin array such that isPalin[i][j] 
# stores whether substring s[i, j] is a palindrome or not
def generatePal(s, isPalin):
    n = len(s)

    # Substring s[i .. i] of len 1 
    # is always palindromic
    for i in range(n):
        isPalin[i][i] = True

    # Iterate over different lengths of substrings
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            # Check whether s[i] == s[j] and the
            # substring between them is a palindrome
            if s[i] == s[j] and (length == 2 or isPalin[i + 1][j - 1]):
              
                # Mark the substring from i to j as a
                # palindrome
                isPalin[i][j] = True

# Function to calculate the minimum number of cuts required
# to make all substrings of 's' palindromic
def palPartition(s):
    n = len(s)

    # 2D array to store whether substring 
    # s[i, j] is a palindrome or not
    isPalin = [[False] * n for _ in range(n)]

    generatePal(s, isPalin)

    # dp[i] stores minimum cuts for Palindrome 
    # Partitioning of substring s[0...i] 
    dp = [n] * n

    # There is no cut required for single character
    # as it is always palindrome
    dp[0] = 0

    # Iterate over the given string
    for i in range(1, n):

        # Check if string 0 to i is palindrome.
        if isPalin[0][i]:
          
            # if palindrome then cuts required is 0
            dp[i] = 0
        else:
            for j in range(i, 0, -1):

                # if substring s[j...i] is palindromic
                # then we can make a cut over here
                if isPalin[j][i]:
                  
                    # update dp[i] with minimum cuts
                    dp[i] = min(dp[i], 1 + dp[j - 1])

    # Return the minimum cuts required 
    # for the entire string 's'
    return dp[n - 1]

if __name__ == "__main__":
    s = "ababbbabbababa"
    print(palPartition(s))

C#

// C# Solution for Palindrome Partitioning Problem
// using Optimised Bottom Up Dynamic Programming
using System;

class GfG {

    // Function to fill isPalin array such that isPalin[i][j] 
    // stores whether substring s[i, j] is a palindrome or not
    static void GeneratePal(string s, bool[,] isPalin) {
        int n = s.Length;

        // Substring s[i .. i] of len 1 
        // is always palindromic
        for (int i = 0; i < n; i++) {
            isPalin[i, i] = true;
        }

        // Iterate over different lengths of substrings
        for (int len = 2; len <= n; len++) {
            for (int i = 0, j = i + len - 1; j < n; i++, j++) {

                // Check whether s[i] == s[j] and the
                // substring between them is a palindrome
                if (s[i] == s[j] && (len == 2 || isPalin[i + 1, j - 1])) {

                    // Mark the substring from i to j as a
                    // palindrome
                    isPalin[i, j] = true;
                }
            }
        }
    }

    // Function to calculate the minimum number of cuts required
    // to make all substrings of 's' palindromic
    static int palPartition(string s) {
        int n = s.Length;

        // 2D array to store whether substring 
        // s[i, j] is a palindrome or not
        bool[,] isPalin = new bool[n, n];

        GeneratePal(s, isPalin);

        // dp[i] stores minimum cuts for Palindrome 
        // Partitioning of substring s[0...i] 
        int[] dp = new int[n];
        Array.Fill(dp, n);

        // There is no cut required for single character
        // as it is always palindrome
        dp[0] = 0;

        // Iterate over the given string
        for (int i = 1; i < n; i++) {

            // Check if string 0 to i is palindrome.
            if (isPalin[0, i]) {
              
                // if palindrome then cuts required is 0
                dp[i] = 0;
            } else {
                for (int j = i; j >= 1; j--) {

                    // if substring s[j...i] is palindromic
                    // then we can make a cut over here
                    if (isPalin[j, i]) {

                        // update dp[i] with minimum cuts
                        dp[i] = Math.Min(dp[i], 1 + dp[j - 1]);
                    }
                }
            }
        }

        // Return the minimum cuts required 
        // for the entire string 's'
        return dp[n - 1];
    }

    static void Main() {
        string s = "ababbbabbababa";
        Console.WriteLine(palPartition(s));
    }
}

JavaScript

// JavaScript Solution for Palindrome Partitioning Problem
// using Optimised Bottom Up Dynamic Programming

// Function to fill isPalin array such that isPalin[i][j] 
// stores whether substring s[i, j] is a palindrome or not
function generatePal(s, isPalin) {
    let n = s.length;

    // Substring s[i .. i] of len 1 
    // is always palindromic
    for (let i = 0; i < n; i++) {
        isPalin[i][i] = true;
    }

    // Iterate over different lengths of substrings
    for (let len = 2; len <= n; len++) {
        for (let i = 0, j = i + len - 1; j < n; i++, j++) {

            // Check whether s[i] == s[j] and the
            // substring between them is a palindrome
            if (s[i] === s[j] && (len === 2 || isPalin[i + 1][j - 1])) {

                // Mark the substring from i to j as a
                // palindrome
                isPalin[i][j] = true;
            }
        }
    }
}

// Function to calculate the minimum number of cuts required
// to make all substrings of 's' palindromic
function palPartition(s) {
    let n = s.length;

    // 2D array to store whether substring 
    // s[i, j] is a palindrome or not
    let isPalin = Array.from({ length: n }, 
                        () => Array(n).fill(false));

    generatePal(s, isPalin);

    // dp[i] stores minimum cuts for Palindrome 
    // Partitioning of substring s[0...i] 
    let dp = new Array(n).fill(n);

    // There is no cut required for single character
    // as it is always palindrome
    dp[0] = 0;

    // Iterate over the given string
    for (let i = 1; i < n; i++) {

        // Check if string 0 to i is palindrome.
        if (isPalin[0][i]) {

            // if palindrome then cuts required is 0
            dp[i] = 0;
        } else {
            for (let j = i; j >= 1; j--) {

                // if substring s[j...i] is palindromic
                // then we can make a cut over here
                if (isPalin[j][i]) {

                    // update dp[i] with minimum cuts
                    dp[i] = Math.min(dp[i], 1 + dp[j - 1]);
                }
            }
        }
    }

    // Return the minimum cuts required 
    // for the entire string 's'
    return dp[n - 1];
}

let s = "ababbbabbababa";
console.log(palPartition(s));

Output

Palindrome pair in an array of words (or strings)

GeeksforGeeks

News

Improve

Similar Reads

Palindrome String Coding Problems

What is a Palindrome String?A string is called a palindrome if the reverse of the string is the same as the original one. Example: “madam”, “racecar”, “12321”. Properties of a Palindrome String:A palindrome string has some properties which are mentioned below: A palindrome string has a symmetric str

Palindrome String

Given a string s, the task is to check if it is palindrome or not. Example: Input: s = "abba"Output: 1Explanation: s is a palindrome Input: s = "abc" Output: 0Explanation: s is not a palindrome Using Two-Pointers - O(n) time and O(1) spaceThe idea is to keep two pointers, one at the beginning (left)

Sentence Palindrome

Given a sentence s, the task is to check if it is a palindrome sentence or not. A palindrome sentence is a sequence of characters, such as a word, phrase, or series of symbols, that reads the same backward as forward after converting all uppercase letters to lowercase and removing all non-alphanumer

Check if actual binary representation of a number is palindrome

Given a non-negative integer n. The problem is to check if binary representation of n is palindrome or not. Note that the actual binary representation of the number is being considered for palindrome checking, no leading 0’s are being considered. Examples : Input : 9 Output : Yes (9)10 = (1001)2 Inp

Print longest palindrome word in a sentence

Given a string str, the task is to print longest palindrome word present in the string str.Examples: Input : Madam Arora teaches Malayalam Output: Malayalam Explanation: The string contains three palindrome words (i.e., Madam, Arora, Malayalam) but the length of Malayalam is greater than the other t

Count palindrome words in a sentence

Given a string str and the task is to count palindrome words present in the string str. Examples: Input : Madam Arora teaches malayalam Output : 3 The string contains three palindrome words (i.e., Madam, Arora, malayalam) so the count is three. Input : Nitin speaks malayalam Output : 2 The string co

Check if characters of a given string can be rearranged to form a palindrome

Given a string, Check if the characters of the given string can be rearranged to form a palindrome. For example characters of "geeksogeeks" can be rearranged to form a palindrome "geeksoskeeg", but characters of "geeksforgeeks" cannot be rearranged to form a palindrome. Recommended PracticeAnagram P

Lexicographically first palindromic string

Rearrange the characters of the given string to form a lexicographically first palindromic string. If no such string exists display message "no palindromic string". Examples: Input : malayalam Output : aalmymlaa Input : apple Output : no palindromic string Simple Approach: 1. Sort the string charact

Longest Non-palindromic substring

Given a string of size n. The task is to find the length of the largest substring which is not a palindrome. Examples: Input : abba Output : 3 Here maximum length non-palindromic substring is 'abb' which is of length '3'. There could be other non-palindromic sub-strings also of length three like 'bb

Minimum insertions to form a palindrome with permutations allowed

Given a string of lowercase letters. Find minimum characters to be inserted in the string so that it can become palindrome. We can change the positions of characters in the string. Examples: Input : geeksforgeeks Output : 2 geeksforgeeks can be changed as: geeksroforskeeg geeksorfroskeeg and many mo

Smallest Palindrome after replacement

Given a string which has some lowercase alphabet characters and one special character dot(.). We need to replace all dots with some alphabet character in such a way that resultant string becomes a palindrome, in case of many possible replacements, we need to choose palindrome string which is lexicog

Remove a character from a string to make it a palindrome

Given a string, we need to check whether it is possible to make this string a palindrome after removing exactly one character from this. Examples: Input : str = “abcba” Output : Yes we can remove character ‘c’ to make string palindrome Input : str = “abcbea” Output : Yes we can remove character ‘e’

Program to print all palindromes in a given range

Given a range of numbers, print all palindromes in the given range. For example if the given range is {10, 115}, then output should be {11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111}We can run a loop from min to max and check every number for palindrome. If the number is a palindrome, we can simply p

Sum of first K even-length Palindrome numbers

Given a integer k, find the sum of first k even-length palindrome numbers. Even length here refers to the number of digits of a number is even. Examples: Input : k = 3 Output : 66 Explanation: 11 + 22 + 33 = 66 (Sum of first three even-length palindrome numbers) Input : 10 Output : 1496 Explanation:

Check if a given string is a rotation of a palindrome

Given a string, check if it is a rotation of a palindrome. For example your function should return true for "aab" as it is a rotation of "aba". Examples: Input: str = "aaaad" Output: 1 // "aaaad" is a rotation of a palindrome "aadaa" Input: str = "abcd" Output: 0 // "abcd" is not a rotation of any p

Make largest palindrome by changing at most K-digits

Given a string containing all digits, we need to convert this string to a palindrome by changing at most K digits. If many solutions are possible then print lexicographically largest one.Examples: Input : str = “43435” k = 3Output : "93939" Explanation:Lexicographically largest palindrome after 3 ch

Minimum number of deletions to make a string palindrome

Given a string of size 'n'. The task is to remove or delete the minimum number of characters from the string so that the resultant string is a palindrome. Note: The order of characters should be maintained. Examples : Input : aebcbdaOutput : 2Remove characters 'e' and 'd'Resultant string will be 'ab

Find longest palindrome formed by removing or shuffling chars from string

Given a string, find the longest palindrome that can be constructed by removing or shuffling characters from the string. Return only one palindrome if there are multiple palindrome strings of longest length. Examples: Input: abc Output: a OR b OR c Input: aabbcc Output: abccba OR baccab OR cbaabc OR

Print all palindrome permutations of a string

Given a string, we need to print all possible palindromes that can be generated using letters of that string. Examples: Input: str = "aabcb" Output: abcba bacab Input: str = "aabbcadad" Output: aabdcdbaa aadbcbdaa abadcdaba abdacadba adabcbada adbacabda baadcdaab badacadab bdaacaadb daabcbaad dabaca

Find all palindromic sub-strings of a given string | Set 2

Given a string, the task is to find all the palindromic sub-strings from the given string.In Set - 1, another approach has been already discussed and that consider only distinct sub-strings but in this equal sub-strings i.e. ll and ll are considered as two sub-strings, not one. Examples: Input : hel

Count of Palindromic substrings in an Index range

Given a string str of small alphabetic characters other than this we will be given many substrings of this string in form of index tuples. We need to find out the count of the palindromic substrings in given substring range. Examples: Input : String str = "xyaabax" Range1 = (3, 5) Range2 = (2, 3) Ou

Longest Possible Chunked Palindrome

Given a string, the task is to return the length of its longest possible chunked palindrome. It means a palindrome formed by substring in the case when it is not formed by characters of the string. For a better understanding look at the example Examples: Input : ghiabcdefhelloadamhelloabcdefghi Outp

Largest palindromic number by permuting digits

Given N(very large), the task is to print the largest palindromic number obtained by permuting the digits of N. If it is not possible to make a palindromic number, then print an appropriate message. Examples : Input : 313551 Output : 531135 Explanations : 531135 is the largest number which is a pali

Make a lexicographically smallest palindrome with minimal changes

Given a string S. Print the lexicographically smallest string possible. You can make minimal changes to the characters in the string and you can permute the string. Examples: Input : S = "aabc" Output : "abba" Input : S = "aabcd" Output : "abcba" Explanation 1:Change the last index "c" to "b", it be

Number of strings of length N with no palindromic sub string

Given two positive integers N, M. The task is to find the number of strings of length N under the alphabet set of size M such that no substrings of size greater than 1 is palindromic. Examples: Input : N = 2, M = 3 Output : 6 In this case, set of alphabet are 3, say {A, B, C} All possible string of

Check if any anagram of a string is palindrome or not

Given an anagram string S of length N, the task is to check whether it can be made palindrome or not. Examples: Input : S = geeksforgeeks Output: NoExplanation: There is no palindrome anagram of given string Input: S = geeksgeeksOutput: YesExplanation: There are palindrome anagrams of given string.

Count maximum-length palindromes in a String

Given a string, count how many maximum-length palindromes are present. (It need not be a substring) Examples: Input : str = "ababa" Output: 2 Explanation : palindromes of maximum of lengths are : "ababa", "baaab" Input : str = "ababab" Output: 4 Explanation : palindromes of maximum of lengths are :

Next higher palindromic number using the same set of digits

Given a palindromic number num having n number of digits. The problem is to find the smallest palindromic number greater than num using the same set of digits as in num. If no such number can be formed then print "Not Possible". The number could be very large and may or may not even fit into long lo

Online algorithm for checking palindrome in a stream

Given a stream of characters (characters are received one by one), write a function that prints 'Yes' if a character makes the complete string palindrome, else prints 'No'. Examples: Input: str[] = "abcba"Output: a Yes // "a" is palindrome b No // "ab" is not palindrome c No // "abc" is not palindro

Palindrome Partitioning

Given a string s, the task is to find the minimum number of cuts needed for palindrome partitioning of the given string. A partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Examples: Input: s = "geek" Output: 2 Explanation: We need to make

Print all Palindromic Partitions of a String using Bit Manipulation

Given a string, find all possible palindromic partitions of a given string. Note that this problem is different from Palindrome Partitioning Problem, there the task was to find the partitioning with minimum cuts in input string. Here we need to print all possible partitions. Example: Input: nitinOut

Count All Palindromic Subsequence in a given String

Given a string s of length n, the task is to count number of palindromic subsequence (need not necessarily be distinct) present in the string s. Example: Input: s = "abcd"Output: 4Explanation: Palindromic subsequence are : "a" ,"b", "c" ,"d" Input: s = "aab"Output: 4Explanation: palindromic subseque

Print Longest Palindromic Subsequence

Given a sequence, print a longest palindromic subsequence of it. Examples : Input : BBABCBCAB Output : BABCBAB The above output is the longest palindromic subsequence of given sequence. "BBBBB" and "BBCBB" are also palindromic subsequences of the given sequence, but not the longest ones. Input : GEE

Minimum Characters to Add at Front for Palindrome

Given a string s, the task is to find the minimum number of characters to be added to the front of s to make it palindrome. A palindrome string is a sequence of characters that reads the same forward and backward. Examples: Input: s = "abc"Output: 2Explanation: We can make above string palindrome as

Palindrome Substring Queries

Given a string and several queries on the substrings of the given input string to check whether the substring is a palindrome or not. Examples : Suppose our input string is “abaaabaaaba” and the queries- [0, 10], [5, 8], [2, 5], [5, 9]We have to tell that the substring having the starting and ending

Palindrome pair in an array of words (or strings)

Given a list of words, find if any of the two words can be joined to form a palindrome. Examples: Input : list[] = {"geekf", "geeks", "or", "keeg", "abc", "bc"} Output : Yes There is a pair "geekf" and "keeg" Input : list[] = {"abc", "xyxcba", "geekst", "or", "keeg", "bc"} Output : Yes There is a pa

Minimum steps to delete a string after repeated deletion of palindrome substrings

Given a string containing characters as integers only. We need to delete all characters of this string in a minimum number of steps wherein in one step we can delete the substring which is a palindrome. After deleting a substring remaining parts are concatenated. Examples: Input : s = “2553432” Outp

Given a number, find the next smallest palindrome

Given a number, find the next smallest palindrome larger than this number. For example, if the input number is "2 3 5 4 5", the output should be "2 3 6 3 2". And if the input number is "9 9 9", the output should be "1 0 0 1". The input is assumed to be an array. Every entry in array represents a dig

Closest Palindrome Number (absolute difference Is min)

Given a number N. our task is to find the closest Palindrome number whose absolute difference with given number is minimum and absolute difference must be greater than 0. Examples: Input : N = 121 Output : 131 or 111 Explanation: Both having equal absolute differencewith the given number.Input : N =

Count palindromic characteristics of a String

Given a string s of length n, count the number of substrings having different types of palindromic characteristics. Palindromic Characteristic is the number of k-palindromes in a string where k lies in range [0, n). A string is 1-palindrome(or simply palindrome) if and only if it reads the same back

Number of positions where a letter can be inserted such that a string becomes palindrome

Given a string str, we need to find the no. of positions where a letter(lowercase) can be inserted so that string becomes a palindrome. Examples: Input : str = "abca" Output : possible palindromic strings: 1) acbca (at position 2) 2) abcba (at position 4) Hence, the output is 2. Input : str = "aaa"

Minimum equal palindromic cuts with rearrangements allowed

Given a string of length n. Find the minimum number of possible cuts after rearranging the string (if required), such that each cut is a palindrome and length of every cut is equal. That is, find the minimum number of palindromes of equal lengths that can be obtained by partitioning the given string

Palindrome by swapping only one character

Given a string, the task is to check if the string can be made palindrome by swapping a character only once. [NOTE: only one swap and only one character should be swapped with another character] Examples: Input : bbg Output : true Explanation: Swap b(1st index) with g. Input : bdababd Output : true

Article Tags :

Practice Tags :

翻译：