26K
0
6 minute read

Palindrome Partitioning Problem

November 9, 2021
Palindrome Partitioning Problem
Table Of Contents
show

Problem Statement

Given a string s, partition s such that every partition of s is a palindrome. Find the minimum number of cuts to form a palindromic partition of s.

Palindrome: A string is called a palindrome when it is read the same way both forwards and backward.

Sample Test Cases

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

Input 1: s = “Coffee”
Output 1: 3
Explanation 1:

From the picture above, it is evident that a minimum of 3 partitions is needed to make a palindromic partition of s.

Input 2: s = “ababbbabbababa”
Output 2: 3
Explanation 2:

From the picture above, it is evident that 3 cuts are needed for this string.

Naive Approach

We can solve this problem naively, using a recursive backtracking-based algorithm. Observe that if the string is a palindrome, we will need 0 cuts for it (this will be the base case for our recursion). Else, we can try to put cuts at all possible positions in the string and try to calculate the number of cuts needed to make a valid palindromic partitioning over all possible combinations of cuts and return the minimum among them.

C++ Implementation

int checkPalindrome(string & s, int start, int end) {
  while (start < end) {
    if (s[start] != s[end]) {
      return 0;
    }
    start++;
    end--;
  }
  return 1;
}
int minimumCuts(string & s, int i, int j) {
  if (checkPalindrome(s, i, j) || i >= j) {
    return 0;
  }
  int answer = INT_MAX;
  int countCuts = -1;
  for (int k = i; k < j; k++) {
    countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
    countCuts += 1;
    answer = min(answer, countCuts);
  }
  return answer;
}
int getMinCuts(string s) {
  int n = s.length();
  return minimumCuts(s, 0, n - 1);
}

Java Implementation

public static int checkPalindrome(String s, int start, int end) {
  while (start < end) {
    if (s.charAt(start) != s.charAt(end)) {
      return 0;
    }
    start++;
    end--;
  }
  return 1;
}
public static int minimumCuts(String s, int i, int j) {
  if (checkPalindrome(s, i, j) == 1 || i >= j) {
    return 0;
  }
  int answer = Integer.MAX_VALUE;
  int countCuts = -1;
  for (int k = i; k < j; k++) {
    countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j);
    countCuts += 1;
    answer = Math.min(answer, countCuts);
  }
  return answer;
}
public static int getMinCuts(String s) {
  int n = s.length();
  return minimumCuts(s, 0, n - 1);
}

Python Implementation

def checkPalindrome(s, start, end):
    while start < end:
        if s[start] != s[end]:
            return 0
        start += 1
        end -= 1
    return 1


def minimumCuts(s, i, j):
    if checkPalindrome(s, i, j) or i >= j:
        return 0
    answer = 999999
    countCuts = -1
    for k in range(i, j):
        countCuts = minimumCuts(s, i, k) + minimumCuts(s, k + 1, j)
        countCuts += 1
        answer = min(answer, countCuts)
    return answer


def getMinCuts(s):
    n = len(s)

Complexity Analysis

  • Time Complexity: Exponential.
  • Space Complexity: O(1) if recursion stack space is excluded.

Memoization Based Approach

Consider the case when we partition a string from say [0, i], [i + 1, j], [j + 1, n] and we know the cost for each of these substrings. Now, if we want to compute the cost for a combination of cuts such the substrings corresponds to [0, i], [i + 1, l], [l + 1, j], [j + 1, n], then in our brute force method we will again compute the costs for the substrings [0, i] and [j + 1, n]. 

So, we can observe that there will be multiple such redundant function calls. To prevent these redundant function calls, we can memoize/cache the results of these function calls in some containers, and recompute them in O(1) when needed. This will reduce our computational complexity from exponential to polynomial time at the trade-off of some extra space.

C++ Code

int checkPalindrome(string & s, int start, int end) {
  while (start < end) {
    if (s[start] != s[end]) {
      return 0;
    }
    start++;
    end--;
  }
  return 1;
}
int minimumCuts(string & s, int i, int j, vector < vector < int >> & dp) {
  if (checkPalindrome(s, i, j) || i >= j) {
    return dp[i][j] = 0;
  }
  if (dp[i][j] != -1) {
    return dp[i][j];
  }
  int answer = INT_MAX;
  int countCuts = -1;
  for (int k = i; k < j; k++) {
    countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
    countCuts += 1;
    answer = min(answer, countCuts);
  }
  dp[i][j] = answer;
  return dp[i][j];
}
int getMinCuts(string s) {
  int n = s.length();
  vector < vector < int >> dp(n + 1, vector < int > (n + 1, -1));
  return minimumCuts(s, 0, n - 1, dp);
}

Java Code

public static int checkPalindrome(String s, int start, int end) {
  while (start < end) {
    if (s.charAt(start) != s.charAt(end)) {
      return 0;
    }
    start++;
    end--;
  }
  return 1;
}
public static int minimumCuts(String s, int i, int j, int[][] dp) {
  if (checkPalindrome(s, i, j) == 1 || i >= j) {
    dp[i][j] = 0;
    return dp[i][j];
  }
  if (dp[i][j] != -1) {
    return dp[i][j];
  }
  int answer = Integer.MAX_VALUE;
  int countCuts = -1;
  for (int k = i; k < j; k++) {
    countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp);
    countCuts += 1;
    answer = Math.min(answer, countCuts);
  }
  dp[i][j] = answer;
  return dp[i][j];
}
public static int getMinCuts(String s) {
  int n = s.length();
  int[][] dp = new int[n + 1][n + 1];
  for (int i = 0; i <= n; i++) {
    Arrays.fill(dp[i], -1);
  }
  return minimumCuts(s, 0, n - 1, dp);
}

Python Code

def checkPalindrome(s, start, end):
    while start < end:
        if s[start] != s[end]:
            return 0
        start += 1
        end -= 1
    return 1


def minimumCuts(s, i, j, dp):
    if checkPalindrome(s, i, j) or i >= j:
        dp[i][j] = 0
        return dp[i][j]
    if dp[i][j] != -1:
        return dp[i][j]
    answer = 999999
    countCuts = -1
    for k in range(i, j):
        countCuts = minimumCuts(s, i, k, dp) + minimumCuts(s, k + 1, j, dp)
        countCuts += 1
        answer = min(answer, countCuts)
    dp[i][j] = answer
    return dp[i][j]


def getMinCuts(s):
    n = len(s)
    dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]
    return minimumCuts(s, 0, n - 1, dp)

Complexity Analysis

  • Time Complexity: O(n2)
  • Space Complexity: O(n2)

Iterative DP Based Approach

We can solve this problem by using Dynamic Programming to compute the results of the overlapping problems shown in the previous example under memoization and storing them in a DP Table. To solve this problem effectively, we will need two DP arrays, as follows, 

  • DP[i][j] = True if the substring from [i, j] is a palindrome, else False.
  • DpCut[i] = Minimum number of cuts required for prefix from 0 to i.

Using these 2 DP arrays, we can compute the answer for the entire string, and the result will be stored in DpCut[string.length – 1]. If we compute the DP array beforehand and then using its results compute the DpCut array, we can further reduce the time complexity of the problem to Quadratic Asymptotics. 

Check the implementation for a better understanding of the approach:

C++ Code – DP Approach

int getMinCuts(string & s) {
  int n = s.length();
  vector < int > DpCut(n);
  int dp[n][n];
  memset(dp, false, sizeof(dp));
  for (int i = 0; i < n; i++) {
    int minimumCuts = i;
    for (int j = 0; j <= i; j++) {
      if (s[i] == s[j]) {
        if (((i < (j + 2) || dp[j + 1][i - 1]))) {
          dp[j][i] = true;
          if (j == 0) {
            minimumCuts = 0;
          } else {
            minimumCuts = min(minimumCuts, DpCut[j - 1] + 1);
          }
        }
      }
    }
    DpCut[i] = minimumCuts;
  }
  return DpCut[n - 1];
}

Java Code – DP Approach

public static int getMinCuts(String s) {
  int n = s.length();
  int[] DpCut = new int[n];
  boolean[][] dp = new boolean[n][n];
  for (int i = 0; i < n; i++) {
    Arrays.fill(dp[i], false);
  }
  for (int i = 0; i < n; i++) {
    int minimumCuts = i;
    for (int j = 0; j <= i; j++) {
      if (s.charAt(i) == s.charAt(j)) {
        if (i < (j + 2) || dp[j + 1][i - 1]) {
          dp[j][i] = true;
          if (j == 0) {
            minimumCuts = 0;
          } else {
            minimumCuts = Math.min(minimumCuts, DpCut[j - 1] + 1);
          }
        }
      }
    }
    DpCut[i] = minimumCuts;
  }
  return DpCut[n - 1];
}

Python Code – DP Approach

def getMinCuts(s):
    n = len(s)
    cutDp = [0] * n
    dp = [[False for i in range(n)] for j in range(n)]
    for i in range(n):
        minimumCuts = i
        for j in range(i + 1):
            if s[i] == s[j]:
                if i < (j + 2) or dp[j + 1][i - 1]:
                    dp[j][i] = True
                    if j == 0:
                        minimumCuts = 0
                    else:
                        minimumCuts = min(minimumCuts, cutDp[j - 1] + 1)
        cutDp[i] = minimumCuts
    return cutDp[n - 1]

Complexity Analysis

  • Time Complexity: O(n2)
  • Space Complexity: O(n2)

FAQs

Q. How to identify that a problem can be solved by Dynamic Programming?
A. A problem can be solved using Dynamic Programming if it contains some Optimal Substructure and Overlapping Subproblems.

Q. Which of the above approaches is expected to be the fastest?
A. The iterative DP approach is expected to be faster in practice than the Recursive Memoization approach because repeated function calls often bring with them some associated overhead which takes some extra time.

0
0
0
0
Share 0
Tweet 0
Pin it 0
Share 0
Share
Share
Share
Tweet
Previous Post
Trailing Zeros In Factorial

Trailing Zeroes in Factorial

November 9, 2021
Next Post
Count to Infinity Problem

Count to Infinity Problem

November 9, 2021
Total
0
Share
0
0
0
0
0