39. Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

Solution:

Approach 1: Use dynamic programming to calculate the no of splits needed for each possible substring In worst case the time complexity will be O(n^3)

Solution:

Approach 2: Use a 2d array to check for palindrome and 1d array to count maxSplits

class Solution
{
public:
    int minCut(string s)
    {

        int n = s.length();

        vector<vector<bool>> palen(n, vector<bool>(n, false));

        vector<int> dp(n + 1);

        for (int i = 0; i <= n; i++)
        {
            dp[i] = i - 1;
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = i; j >= 0; j--)
            {
                if (i - j == 0)
                {
                    palen[i][j] = true;
                    dp[i + 1] = min(dp[i] + 1, dp[i + 1]);
                }

                if (i - j == 1)
                {
                    if (s[i] == s[j])
                    {
                        palen[j][i] = true;
                        dp[i + 1] = min(dp[j] + 1, dp[i + 1]);
                    }
                }

                if (i - j > 1)
                {
                    if (s[i] == s[j] && palen[j + 1][i - 1])
                    {
                        palen[j][i] = true;
                        dp[i + 1] = min(dp[i + 1], dp[j] + 1);
                    }
                }
            }
        }

        return dp[n];
    }
};

Time Complexity: O(n^2)