LeetCode 1745 - Palindrome Partitioning IV

The problem asks us to determine whether a given string s can be split into exactly three non-empty substrings, each of which is a palindrome. A palindrome is a string that reads the same forward and backward. For example, the string "aba" is a palindrome, whereas "abc" is not.

leetcodehardstringdynamic-programming

LeetCode Problem 1745

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine whether a given string s can be split into exactly three non-empty substrings, each of which is a palindrome. A palindrome is a string that reads the same forward and backward. For example, the string "aba" is a palindrome, whereas "abc" is not. The input s is guaranteed to have a length of at least 3 and at most 2000 characters, and it consists entirely of lowercase English letters.

The output is a boolean value: true if such a partition exists, false otherwise. Importantly, each of the three substrings must be non-empty, which means trivial partitions like one empty substring are invalid.

Key edge cases include strings that are entirely palindromic (e.g., "aaa") or strings that contain repeated characters but cannot form three palindromes of at least length 1 each. Also, strings of length exactly 3 are interesting because each character must individually be a palindrome.

Approaches

The brute-force approach would be to try all possible ways to split the string into three parts and check if each part is a palindrome. This involves nested loops for the first and second cuts. While it guarantees correctness, it is too slow for the maximum input size because it results in O(n^3) complexity: O(n^2) splits, and each substring check for a palindrome takes O(n) time.

A key observation for an optimal solution is that we can precompute all palindromic substrings using dynamic programming. By building a 2D boolean table dp[i][j] representing whether the substring s[i:j+1] is a palindrome, we can then efficiently check all possible splits in O(n^2) time. This reduces the repeated work of checking palindromes multiple times.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Try every split and check if each part is a palindrome
Optimal O(n^2) O(n^2) Precompute palindrome table and check splits efficiently

Algorithm Walkthrough

  1. Initialize a 2D boolean array dp of size n x n where dp[i][j] will be True if the substring s[i:j+1] is a palindrome.
  2. Fill the dp table using the rule that a substring is a palindrome if its endpoints match and the inner substring is a palindrome. For length 1 substrings, mark as True, and for length 2, mark True if both characters match.
  3. Iterate over all possible first cuts i from 1 to n-2. This defines the first substring s[0:i].
  4. For each first cut, iterate over all possible second cuts j from i+1 to n-1. This defines the second substring s[i:j] and third substring s[j:n].
  5. For each pair of cuts (i,j), check if dp[0][i-1], dp[i][j-1], and dp[j][n-1] are all True.
  6. If such a split exists, return True. If no split works, return False.

Why it works: The dp table guarantees that checking whether a substring is a palindrome is O(1). By iterating over all valid cut positions, we ensure that every possible three-part partition is considered. Therefore, if a valid partition exists, it will be found.

Python Solution

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        
        for length in range(1, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if length == 1:
                    dp[i][j] = True
                elif length == 2:
                    dp[i][j] = s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
        
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:
                    return True
        return False

This implementation first constructs a palindrome table dp where each cell dp[i][j] tells if s[i:j+1] is a palindrome. The two nested loops check every valid two-cut configuration to see if all three resulting substrings are palindromes.

Go Solution

func checkPartitioning(s string) bool {
    n := len(s)
    dp := make([][]bool, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]bool, n)
    }

    for length := 1; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if length == 1 {
                dp[i][j] = true
            } else if length == 2 {
                dp[i][j] = s[i] == s[j]
            } else {
                dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
            }
        }
    }

    for i := 1; i < n-1; i++ {
        for j := i + 1; j < n; j++ {
            if dp[0][i-1] && dp[i][j-1] && dp[j][n-1] {
                return true
            }
        }
    }
    return false
}

The Go implementation mirrors the Python logic, using slices for the DP table. All substring comparisons use byte indexing since strings are immutable in Go.

Worked Examples

Example 1: s = "abcbdd"

  1. Build dp table: dp[0][2] = False, dp[1][3] = True for "bcb", dp[4][5] = True for "dd".
  2. Check splits: first cut i=1 ("a"), second cut j=4 ("bcb"), last substring "dd" - all are palindromes.
  3. Return True.

Example 2: s = "bcbddxy"

  1. Build dp table: only palindromes are "b", "c", "b", "d", "d", "x", "y" and "bcb".
  2. Check all splits: no combination gives three palindromes.
  3. Return False.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Building the DP table takes O(n^2) and checking all cuts also takes O(n^2)
Space O(n^2) The DP table stores palindromic state for all substrings

The quadratic time is acceptable given the constraint n <= 2000, and using a DP table avoids repeated palindrome checks.

Test Cases

# Basic examples
assert Solution().checkPartitioning("abcbdd") == True  # splits: "a", "bcb", "dd"
assert Solution().checkPartitioning("bcbddxy") == False # no valid split

# Edge cases
assert Solution().checkPartitioning("aaa") == True      # splits: "a", "a", "a"
assert Solution().checkPartitioning("abc") == False     # cannot split into 3 palindromes
assert Solution().checkPartitioning("abccbaabccba") == True # multiple palindromic options

# Larger input stress
assert Solution().checkPartitioning("a"*2000) == True   # entire string is palindromic
assert Solution().checkPartitioning("a"*1999 + "b") == False # last char breaks palindromes
Test Why
"abcbdd" Standard example with valid three palindromes
"bcbddxy" Standard example with no valid split
"aaa" Minimum length with all identical chars
"abc" Minimum length with distinct chars, invalid split
"abccbaabccba" Multiple palindromic substrings, ensures DP correctness
"a"*2000 Large uniform string stress test
"a"*1999 + "b" Edge stress test with near-palindrome

Edge Cases

One important edge case is when the string has exactly three characters. Each character individually must be a palindrome. The algorithm handles this naturally since dp[i][j] marks single characters as palindromes.

Another edge case occurs when the string is entirely composed of the same character. This could lead a naive algorithm to try invalid splits if it does not ensure three non-empty substrings. Using the two nested loops for cuts ensures non-empty partitions.

Finally, a string where only one substring in the middle is palindromic and the others are not could be tricky. The DP table guarantees that the substring checks are correct in constant time,