Palindrome Partitioning 2 Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/max-path-sum-matrix

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Find the minimum cuts needed for palindromic partition of s.

Naive Approach

 Observe that if the string is a palindrome, we can simply return 0. Else, we can recursively try to make cuts at all possible positions and try to compute the cost for all possible combinations of cuts and return the minimum value among them.

Analysis

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

Implementation

C++

int palindrome(string s, int start, int end) {
	while(start < end) {
		if(s[start] != s[end]) {
			return 0;
		}
		start++;
		end--;
	}
	return 1;
}
int minCuts(string s, int i, int j) {
	if(palindrome(s, i, j) == 1 || j <= i) {
		return 0;
	}
	int result = INT_MAX, cutCounter;
	for(int k = i; k < j; k++) {
		cutCounter = minCuts(s, i, k) + minCuts(s, k + 1, j) + 1;
		result = min(result, cutCounter);
	}
	return result;
}
int getMinCuts(string s) {
    return minCuts(s, 0, s.size() - 1);
}

Java

class Solution {
	int palindrome(String s, int start, int end) {
		while(start < end) {
			if(s.charAt(start) != s.charAt(end)) {
				return 0;
			}
			start++;
			end--;
		}
		return 1;
	}
	int minCuts(String s, int i, int j) {
		if(palindrome(s, i, j) == 1 || j <= i) {
			return 0;
		}
		int result = Integer.MAX_VALUE, cutCounter;
		for(int k = i; k < j; k++) {
			cutCounter = minCuts(s, i, k) + minCuts(s, k + 1, j) + 1;
			result = Math.min(result, cutCounter);
		}
		return result;
	}
	int getMinCuts(String s) {
	    return minCuts(s, 0, s.length() - 1);
	}
}

Optimal Approach

We can optimize the above naive approach by using Dynamic Programming. Observe that many of the recursive calls are getting repeated again and again. We can tabulate these values in a DP table, to avoid them being recalculated. This problem is a variation of the Matrix Chain Multiplication problem.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n²)

Implementation (Iterative)

C++

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

Java

class Solution {
	int getMinCuts(String s) {
	    int cutDp[] = new int[s.length()];
		boolean dp[][] = new boolean[s.length()][s.length()];
		for(int i = 0; i < s.length(); i++) {
			for(int j = 0; j < s.length(); j++) {
				dp[i][j] = false;
			}
		}
		for(int i = 0; i < s.length(); 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, cutDp[j - 1] + 1);
						}
					}
				}
			}
			cutDp[i] = minimumCuts;
		}
		return cutDp[s.length() - 1];
	}
}

Implementation(Recursive)

C++

bool palindrome(string s, int start, int end) {
	while(start < end) {
		if(s[start] != s[end]) {
			return false;
		}
		start++;
		end--;
	}
	return true;
}
int minCuts(string &s, int i, int j, vector<vector<int>> &dp) {
	if(dp[i][j] != -1) {
		return dp[i][j];
	}
	if(palindrome(s, i, j) || j <= i) {
		return dp[i][j] = 0;
	}
	int result = INT_MAX, cutCounter;
	for(int k = i; k < j; k++) {
		cutCounter = minCuts(s, i, k, dp) + minCuts(s, k + 1, j, dp) + 1;
		result = min(result, cutCounter);
	}
	return dp[i][j] = result;
}
int getMinCuts(string s) {
	vector<vector<int>> dp(s.size() + 1, vector<int> (s.size() + 1, -1));
    return minCuts(s, 0, s.size() - 1, dp);
}

Java

class Solution {
	int[][] dp;
	int palindrome(String s, int start, int end) {
		while(start < end) {
			if(s.charAt(start) != s.charAt(end)) {
				return 0;
			}
			start++;
			end--;
		}
		return 1;
	}
	int minCuts(String s, int i, int j) {
		if(palindrome(s, i, j) == 1 || j <= i) {
			return 0;
		}
		if(dp[i][j] != -1) {
			return dp[i][j];
		}
		int result = Integer.MAX_VALUE, cutCounter;
		for(int k = i; k < j; k++) {
			cutCounter = minCuts(s, i, k) + minCuts(s, k + 1, j) + 1;
			result = Math.min(result, cutCounter);
		}
		return dp[i][j] = result;
	}
	int getMinCuts(String s) {
		dp = new int[s.length() + 1][s.length() + 1];
		for(int i = 0; i <= s.length(); i++) {
			Arrays.fill(dp[i], -1);
		}
	    return minCuts(s, 0, s.length() - 1);
	}
}