Palindrome Partition

Given a string, a partitioning of the string is a palindrome partitioning if every partition is a palindrome.

For example, “aba |b | bbabb |a| b| aba” is a palindrome partitioning of “ababbbabbababa”.

Determine the fewest cuts needed for palindrome partitioning of a given string.

For example,

minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a | babbbab | b | ababa”.

If a string is palindrome, then minimum 0 cuts are needed.

Return the minimum cuts.

Solution: Dp, incremental cuts

Base Case: 0 letters, and 1 letter don't need to be cut

Induction Rule:

1. Check every increment

2. Check every cut

3. if right cut is a palindrome, Check if left cut + 1 is best cut so far

private boolean checkPali(String input, int left, int right){
    if (left >= right) return true;
    while (right > left){
        if (input.charAt(left) != input.charAt(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

public int paliPart(String input){
    if(input == null || input.length() <= 1) return 0;
    int[] M = new int[input.length() + 1];
    M[0] = 0; M[1] = 0;
    for (int i = 2; i <= input.length(); i++){ //check every increment
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < i; j++){ //check every cut
            if (checkPali(input, j, i - 1)){
                min = j == 0 ? 0 : Math.min(min, M[j] + 1);
            }
        }
        M[i] = min == Integer.MAX_VALUE ? -1 : min;
    }
    return M[input.length()];
}
    

Time Complexity: O(N) increment check * O(N) cut check * O(N) checkPali = O(N^3)

Space Complexity: O(N)

0 1 2 3 4 5

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Extra Space Optimization: Memoize palindrome segments

Using O(N^2) space we can track validity of segments.

int[][] paliCheck //is i -> j a palindrome
int[] cuts // min cuts for 0 -> i

Reducing validity check to O(1) means time complexity turns into O(N^2)