Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1745. Palindrome Partitioning IV - Leetcode Solution

Code Implementation

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        # Precompute palindrome substrings
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n):
            is_pal[i][i] = True
        for i in range(n-1):
            is_pal[i][i+1] = (s[i] == s[i+1])
        for length in range(3, n+1):
            for i in range(n-length+1):
                j = i + length - 1
                is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
        # Try all possible two cuts
        for i in range(1, n-1):
            for j in range(i, n-1):
                if is_pal[0][i-1] and is_pal[i][j] and is_pal[j+1][n-1]:
                    return True
        return False
    
class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> is_pal(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i) is_pal[i][i] = true;
        for (int i = 0; i + 1 < n; ++i) is_pal[i][i+1] = (s[i] == s[i+1]);
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                is_pal[i][j] = (s[i] == s[j]) && is_pal[i+1][j-1];
            }
        }
        for (int i = 1; i < n-1; ++i) {
            for (int j = i; j < n-1; ++j) {
                if (is_pal[0][i-1] && is_pal[i][j] && is_pal[j+1][n-1])
                    return true;
            }
        }
        return false;
    }
};
    
class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int i = 0; i < n; i++) isPal[i][i] = true;
        for (int i = 0; i + 1 < n; i++) isPal[i][i+1] = (s.charAt(i) == s.charAt(i+1));
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                isPal[i][j] = (s.charAt(i) == s.charAt(j)) && isPal[i+1][j-1];
            }
        }
        for (int i = 1; i < n-1; i++) {
            for (int j = i; j < n-1; j++) {
                if (isPal[0][i-1] && isPal[i][j] && isPal[j+1][n-1]) {
                    return true;
                }
            }
        }
        return false;
    }
}
    
var checkPartitioning = function(s) {
    const n = s.length;
    const isPal = Array.from({length: n}, () => Array(n).fill(false));
    for (let i = 0; i < n; ++i) isPal[i][i] = true;
    for (let i = 0; i + 1 < n; ++i) isPal[i][i+1] = (s[i] === s[i+1]);
    for (let len = 3; len <= n; ++len) {
        for (let i = 0; i + len - 1 < n; ++i) {
            let j = i + len - 1;
            isPal[i][j] = (s[i] === s[j]) && isPal[i+1][j-1];
        }
    }
    for (let i = 1; i < n-1; ++i) {
        for (let j = i; j < n-1; ++j) {
            if (isPal[0][i-1] && isPal[i][j] && isPal[j+1][n-1]) {
                return true;
            }
        }
    }
    return false;
};

Problem Description

Given a string s, determine if it is possible to split s into exactly three non-empty substrings such that each substring is a palindrome. Each substring must be contiguous, and every character in s must be used in exactly one substring. You must return true if at least one such partition exists, and false otherwise.
  • Each substring must be non-empty and contiguous.
  • All three substrings must be palindromes.
  • Every character from s must be included in exactly one substring.
  • There is no need to enumerate all partitions—just determine if at least one valid partition exists.

Thought Process

At first glance, the problem seems to suggest checking all possible ways to split the string into three parts and testing each for the palindrome property. However, this brute-force approach would be inefficient for longer strings, as the number of possible splits grows quadratically with the length of the string. Instead, we can optimize by:
  • Precomputing which substrings are palindromes, so we can check any substring in constant time.
  • Iterating through all possible positions to cut the string into three parts, and using our precomputed data to check if each part is a palindrome.
This approach leverages dynamic programming for palindrome checking and reduces redundant work.

Solution Approach

To efficiently solve the problem, we use the following steps:
  1. Precompute Palindrome Substrings:
    • Create a 2D array is_pal[i][j] that is true if the substring s[i..j] is a palindrome.
    • Initialize all substrings of length 1 as palindromes.
    • Initialize all substrings of length 2 as palindromes if both characters are equal.
    • For substrings longer than 2, use dynamic programming: s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is a palindrome.
  2. Check All Possible Splits:
    • We need to split s into three non-empty parts, so the first cut can be at any position i (from 1 to n-2), and the second cut at any position j (from i to n-2).
    • For each possible (i, j) pair, check if s[0..i-1], s[i..j], and s[j+1..n-1] are all palindromes using our precomputed array.
    • If any such split is found, return true.
  3. Return the Result:
    • If no valid split is found after checking all possibilities, return false.
This method ensures we never check the same substring more than once for the palindrome property, making the solution efficient.

Example Walkthrough

Consider the input s = "abcbdd".
  • First, we precompute all palindromic substrings. For example, "a", "b", "c", "b", "d", "d" are all palindromes by default. "bcb" is also a palindrome.
  • We try all possible splits:
    • First cut at i = 1, second cut at j = 1:
      • s[0..0] = "a" (palindrome)
      • s[1..1] = "b" (palindrome)
      • s[2..5] = "cbdd" (not a palindrome)
    • Try i = 1, j = 2:
      • s[0..0] = "a" (palindrome)
      • s[1..2] = "bc" (not a palindrome)
    • Try i = 1, j = 3:
      • s[0..0] = "a" (palindrome)
      • s[1..3] = "bcb" (palindrome)
      • s[4..5] = "dd" (palindrome)
    • All three are palindromes! The function returns true.
This demonstrates how the function finds a valid partition without checking all possible combinations exhaustively.

Time and Space Complexity

  • Brute-force:
    • There are O(n2) ways to split the string into three parts.
    • Checking if each substring is a palindrome takes up to O(n) time each, so overall O(n3).
  • Optimized Approach:
    • Precomputing the palindrome table takes O(n2) time and space.
    • Checking all splits is O(n2), and each palindrome check is O(1) due to precomputation.
    • Overall time complexity: O(n2)
    • Space complexity: O(n2) for the palindrome table.

Summary

In summary, the problem asks whether a string can be split into three contiguous palindromic substrings. By precomputing all palindromic substrings using dynamic programming, we can efficiently check all possible ways to partition the string with two cuts. This results in an elegant O(n2) solution that avoids redundant palindrome checks, making the approach both efficient and easy to understand.