# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/palindrome-partition.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.