Problem

Given a string, split it into as few strings as possible such that each string is a palindrome.

Examples

Example 1

1
2
3

Input: "aab"
Output: ["aa", "b"]
Explanation: The string "aab" can be split into ["aa", "b"], where both "aa" and "b" are palindromes.

Example 2

1
2
3

Input: "racecarannakayak"
Output: ["racecar", "anna", "kayak"]
Explanation: The string "racecarannakayak" can be split into ["racecar", "anna", "kayak"], where each substring is a palindrome.

Solution

Method 1 - DP

To solve this problem, we can use dynamic programming to keep track of the minimum cuts needed to partition the string into palindromic substrings. Here’s the detailed approach:

Approach

  1. Dynamic Programming Table: Create a table dp where dp[i] represents the minimum number of cuts needed to partition the substring s[0:i+1] into palindromic substrings.
  2. Palindrome Table: Create a 2D table palindrome where palindrome[i][j] is True if the substring s[i:j+1] is a palindrome.
  3. Initialization: Initialize the palindrome table. If s[i] == s[j] and the substring between them is also a palindrome, then palindrome[i][j] is True.
  4. Filling DP Table: Iterate through the string to fill in the dp table using the palindrome table to determine the minimum cuts required.
  5. Backtracking: Use the dp table to backtrack and find the palindromic substrings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class Solution {
    public List<String> minCutPalindromes(String s) {
        int n = s.length();
        boolean[][] palindrome = new boolean[n][n];
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            palindrome[i][i] = true;
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    palindrome[i][j] = (len == 2) || palindrome[i + 1][j - 1];
                } else {
                    palindrome[i][j] = false;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (palindrome[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = Integer.MAX_VALUE;
                for (int j = 0; j < i; j++) {
                    if (palindrome[j + 1][i] && dp[j] + 1 < dp[i]) {
                        dp[i] = dp[j] + 1;
                    }
                }
            }
        }
        
        List<String> result = new ArrayList<>();
        int index = n - 1;
        while (index >= 0) {
            for (int j = 0; j <= index; j++) {
                if (palindrome[j][index] && (j == 0 || dp[j - 1] + 1 == dp[index])) {
                    result.add(0, s.substring(j, index + 1));
                    index = j - 1;
                    break;
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minCutPalindromes("aab")); 
        System.out.println(solution.minCutPalindromes("racecarannakayak"));
        System.out.println(solution.minCutPalindromes("abac"));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution:
    def minCutPalindromes(self, s: str) -> List[str]:
        n = len(s)
        dp = [0] * n
        palindrome = [[False] * n for _ in range(n)]
        
        for i in range(n):
            palindrome[i][i] = True
        
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    palindrome[i][j] = (length == 2) or palindrome[i + 1][j - 1]
                else:
                    palindrome[i][j] = False
        
        for i in range(n):
            if palindrome[0][i]:
                dp[i] = 0
            else:
                dp[i] = float('inf')
                for j in range(i):
                    if palindrome[j + 1][i] and dp[j] + 1 < dp[i]:
                        dp[i] = dp[j] + 1
        
        result = []
        index = n - 1
        while index >= 0:
            for j in range(index + 1):
                if palindrome[j][index] and (j == 0 or dp[j - 1] + 1 == dp[index]):
                    result.insert(0, s[j:index + 1])
                    index = j - 1
                    break
        
        return result

# Example usage
sol = Solution()
print(sol.minCutPalindromes("aab"))  # Output: ["aa", "b"]
print(sol.minCutPalindromes("racecarannakayak"))  # Output: ["racecar", "anna", "kayak"]
print(sol.minCutPalindromes("abac"))  # Output: ["a", "b", "a", "c"]

Complexity

  • ⏰ Time complexity: O(n^2) for filling the dp and palindrome tables.
  • 🧺 Space complexity: O(n^2) for storing the dp and palindrome tables.

Method 2 -

Code

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)