Palindrome Partitioning II In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

Problem: Palindrome Partitioning II

Problem Statement:

Given a string s, you need to partition s into the minimum number of substrings such that each substring is a palindrome. Return the minimum number of cuts required to achieve this partition.

A palindrome is a string that reads the same backward as forward.

Example 1:

Input:

pythonCopy codes = "aab"

Output:

pythonCopy code1

Explanation: The optimal partition is "aa", "b". Only one cut is needed.

Example 2:

Input:

pythonCopy codes = "a"

Output:

pythonCopy code0

Explanation: The string “a” is already a palindrome, so no cuts are needed.

Example 3:

Input:

pythonCopy codes = "ab"

Output:

pythonCopy code1

Explanation: The optimal partition is "a", "b". One cut is required.

Approach:

To solve this problem efficiently, we can use Dynamic Programming (DP). The key idea is to break down the problem into subproblems where:

  • We find the minimum cuts needed for each substring.
  • We also track whether a substring is a palindrome or not.

Dynamic Programming Approach:

  1. Palindrome Check:
    • First, we need to preprocess the string to check if each substring is a palindrome. This can be stored in a 2D DP table isPalindrome[i][j], where isPalindrome[i][j] = true if the substring s[i..j] is a palindrome.
  2. DP Array for Minimum Cuts:
    • We use a DP array dp[i] where dp[i] represents the minimum number of cuts needed for the substring s[0..i]. Initially, we assume the worst case, where every character needs a cut.
    • If s[i..j] is a palindrome (for all 0 <= j <= i), we can update the dp[i] to be dp[j-1] + 1.
  3. Base Case:
    • If the string from index 0 to i is already a palindrome, no cuts are needed, so dp[i] = 0.
  4. Final Answer:
    • The final answer will be stored in dp[n-1], where n is the length of the string.

Time Complexity:

  • Time Complexity: O(N2)O(N^2)O(N2), where N is the length of the string. This is because we need to fill the DP table for palindrome checks and calculate the minimum cuts.
  • Space Complexity: O(N2)O(N^2)O(N2), for storing the DP table for palindrome checks.

Algorithm Implementation

Python Code

pythonCopy codedef minCut(s):
    n = len(s)
    
    # Step 1: Precompute palindrome table
    isPalindrome = [[False] * n for _ in range(n)]
    
    for i in range(n):
        isPalindrome[i][i] = True  # A single character is always a palindrome
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            isPalindrome[i][i + 1] = True  # Two consecutive characters are a palindrome if they are the same
    
    # Fill the palindrome table
    for length in range(3, n + 1):  # Check for palindromes of length 3 to n
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and isPalindrome[i + 1][j - 1]:
                isPalindrome[i][j] = True
    
    # Step 2: DP array to find the minimum cuts
    dp = [0] * n
    for i in range(n):
        if isPalindrome[0][i]:
            dp[i] = 0  # No cuts needed if the entire substring is a palindrome
        else:
            dp[i] = float('inf')
            for j in range(i):
                if isPalindrome[j + 1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n - 1]

# Example test cases
print(minCut("aab"))  # Output: 1
print(minCut("a"))    # Output: 0
print(minCut("ab"))   # Output: 1

C++ Code

cppCopy code#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    int minCut(string s) {
        int n = s.length();
        
        // Step 1: Precompute palindrome table
        vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
        
        for (int i = 0; i < n; ++i) {
            isPalindrome[i][i] = true;  // A single character is always a palindrome
        }
        
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == s[i + 1]) {
                isPalindrome[i][i + 1] = true;  // Two consecutive characters are palindrome if they are the same
            }
        }
        
        // Fill the palindrome table
        for (int length = 3; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                if (s[i] == s[j] && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }
        
        // Step 2: DP array to find the minimum cuts
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            if (isPalindrome[0][i]) {
                dp[i] = 0;  // No cuts needed if the entire substring is a palindrome
            } else {
                dp[i] = INT_MAX;
                for (int j = 0; j < i; ++j) {
                    if (isPalindrome[j + 1][i]) {
                        dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
};

int main() {
    Solution solution;
    cout << solution.minCut("aab") << endl;  // Output: 1
    cout << solution.minCut("a") << endl;    // Output: 0
    cout << solution.minCut("ab") << endl;   // Output: 1
    return 0;
}

Java Code

javaCopy codeimport java.util.*;

public class Solution {
    public int minCut(String s) {
        int n = s.length();
        
        // Step 1: Precompute palindrome table
        boolean[][] isPalindrome = new boolean[n][n];
        
        for (int i = 0; i < n; ++i) {
            isPalindrome[i][i] = true;  // A single character is always a palindrome
        }
        
        for (int i = 0; i < n - 1; ++i) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                isPalindrome[i][i + 1] = true;  // Two consecutive characters are palindrome if they are the same
            }
        }
        
        // Fill the palindrome table
        for (int length = 3; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }
        
        // Step 2: DP array to find the minimum cuts
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            if (isPalindrome[0][i]) {
                dp[i] = 0;  // No cuts needed if the entire substring is a palindrome
            } else {
                dp[i] = Integer.MAX_VALUE;
                for (int j = 0; j < i; ++j) {
                    if (isPalindrome[j + 1][i]) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minCut("aab"));  // Output: 1
        System.out.println(solution.minCut("a"));    // Output: 0
        System.out.println(solution.minCut("ab"));   // Output: 1
    }
}

C# Code

csharpCopy codeusing System;
using System.Collections.Generic;

public class Solution {
    public int MinCut(string s) {
        int n = s.Length;

        // Step 1: Precompute palindrome table
        bool[,] isPalindrome = new bool[n, n];

        for (int i = 0; i < n; ++i) {
            isPalindrome[i, i] = true;  // A single character is always a palindrome
        }

        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == s[i + 1]) {
                isPalindrome[i, i + 1] = true;  // Two consecutive characters are palindrome if they are the same
            }
        }

        // Fill the palindrome table
        for (int length = 3; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                if (s[i] == s[j] && isPalindrome[i + 1, j - 1]) {
                    isPalindrome[i, j] = true;
                }
            }
        }

        // Step 2: DP array to find the minimum cuts
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            if (isPalindrome[0, i]) {
                dp[i] = 0;  // No cuts needed if the entire substring is a palindrome
            } else {
                dp[i] = int.MaxValue;
                for (int j = 0; j < i; ++j) {
                    if (isPalindrome[j + 1, i]) {
                        dp[i] = Math.Min(dp[i], dp[j] + 1);
                    }
                }
            }
        }

        return dp[n - 1];
    }

    public static void Main() {
        Solution solution = new Solution();
        Console.WriteLine(solution.MinCut("aab"));  // Output: 1
        Console.WriteLine(solution.MinCut("a"));    // Output: 0
        Console.WriteLine(solution.MinCut("ab"));   // Output: 1
    }
}

JavaScript Code

javascriptCopy codefunction minCut(s) {
    const n = s.length;
    
    // Step 1: Precompute palindrome table
    const isPalindrome = Array.from({ length: n }, () => Array(n).fill(false));
    
    for (let i = 0; i < n; i++) {
        isPalindrome[i][i] = true;  // A single character is always a palindrome
    }
    
    for (let i = 0; i < n - 1; i++) {
        if (s[i] === s[i + 1]) {
            isPalindrome[i][i + 1] = true;  // Two consecutive characters are palindrome if they are the same
        }
    }
    
    // Fill the palindrome table
    for (let length = 3; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (s[i] === s[j] && isPalindrome[i + 1][j - 1]) {
                isPalindrome[i][j] = true;
            }
        }
    }
    
    // Step 2: DP array to find the minimum cuts
    const dp = Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            dp[i] = 0;  // No cuts needed if the entire substring is a palindrome
        } else {
            dp[i] = Infinity;
            for (let j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    
    return dp[n - 1];
}

// Example usage
console.log(minCut("aab"));  // Output: 1
console.log(minCut("a"));    // Output: 0
console.log(minCut("ab"));   // Output: 1

C

#include <stdio.h>
#include <string.h>
#include <limits.h>

// Function to find the minimum cuts for palindrome partitioning
int minCut(char *s) {
    int n = strlen(s);
    
    // Step 1: Precompute palindrome table
    int isPalindrome[n][n];
    memset(isPalindrome, 0, sizeof(isPalindrome));
    
    // Every single character is a palindrome
    for (int i = 0; i < n; i++) {
        isPalindrome[i][i] = 1;
    }
    
    // Check two consecutive characters
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            isPalindrome[i][i + 1] = 1;
        }
    }
    
    // Fill the palindrome table for substrings of length 3 to n
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && isPalindrome[i + 1][j - 1]) {
                isPalindrome[i][j] = 1;
            }
        }
    }
    
    // Step 2: DP array to find the minimum cuts
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = INT_MAX;
    }
    
    for (int i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            dp[i] = 0;  // No cuts needed if the entire substring s[0..i] is a palindrome
        } else {
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : (dp[j] + 1);
                }
            }
        }
    }
    
    return dp[n - 1];
}

int main() {
    // Test cases
    char s1[] = "aab";
    char s2[] = "a";
    char s3[] = "ab";
    
    printf("Minimum cuts for \"%s\": %d\n", s1, minCut(s1));  // Output: 1
    printf("Minimum cuts for \"%s\": %d\n", s2, minCut(s2));  // Output: 0
    printf("Minimum cuts for \"%s\": %d\n", s3, minCut(s3));  // Output: 1
    
    return 0;

Summary:

  • Dynamic Programming is used to solve this problem efficiently by precomputing whether each substring is a palindrome.
  • The algorithm constructs the minimum cuts array based on whether the substring s[i..j] is a palindrome.
  • The final answer will be in the dp[n-1], where n is the length of the string.

Time Complexity:

  • Time Complexity: O(N^2)due to the palindrome table computation and the subsequent DP updates.
  • Space Complexity: O(N^2) for storing the palindrome table.