Palindrome Partitioning Ii - Leetcode Solution

Problem Statement:

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

Constraints:

1 <= s.length <= 2000 s consists of lower-case English letters only.

Solution:

Approach:

The problem requires us to find the minimum number of cuts required to partition a string s into palindromic substrings. This can be done by using Dynamic Programming.

We can use the following approach to solve this problem:

Step 1: Initialize a one-dimensional DP array dp of size n + 1, where n is the length of the string. Here dp[i] will store the minimum number of cuts required to partition the string s[0..i-1] into palindromic substrings.

Step 2: Initialize each element of the array as its index value.

Step 3: Traverse the array from the second character to the end of the string.

Step 4: For each character i, traverse the array from the start to i.

Step 5: If the current substring s[j..i] is a palindrome, update the minimum cuts required to partition the string s[0..i-1].

The minimum cuts required will be dp[j] + 1, where dp[j] is the minimum number of cuts required to partition the string s[0..j-1] into palindromic substrings, and the additional cut 1 is made to include the current palindrome string s[j..i]. We take minimum of all such values as we want the minimum number of cuts possible.

Step 6: Return dp[n] - 1, as we're working on 0-based indexing and this will be the final answer.

Code:

The code implementation of the above approach is given below:

class Solution { public: int minCut(string s) { int n = s.length();

    vector<int> dp(n + 1, 0);
    for(int i = 0;i <= n;i++)
        dp[i] = i - 1;
    
    for(int i = 1;i < n;i++) {
        for(int j = 0;j <= i;j++) {
            if(isPalindrome(s, j, i)) {
                dp[i + 1] = min(dp[i + 1], dp[j] + 1);
            }
        }
    }
    return dp[n];
}

private: bool isPalindrome(string s, int i, int j) { while(i < j) { if(s[i] != s[j]) return false; i++; j--; } return true; } };

Time Complexity:

The time complexity of the solution is O(n^2) as we're traversing two loops for i and j, and checking palindrome string takes O(n).

Space Complexity:

The space complexity of the solution is O(n), as we're using a dp array of size n.

1