Palindrome Partitioning IV: Three-Way Palindrome Split

Given a string s, return true if it is possible to split s into three non-empty substrings such that each substring is a palindrome. This is LeetCode 1745: Palindrome Partitioning IV, a hard-level string problem that builds directly on the palindrome DP technique you may already know from easier palindrome problems.

Why this problem matters

At first glance, this looks like it should be simple. You just need to find two places to cut the string so that all three pieces read the same forward and backward. But the naive approach of checking every pair of cut positions and then verifying each piece character by character leads to O(n^3) time, which is too slow for strings up to length 2000.

The real challenge is recognizing that palindrome checking is the bottleneck, and that you can precompute all palindrome information in O(n^2) time using dynamic programming. Once you have that table, each three-way partition check becomes three O(1) lookups.

This problem is also a great test of whether you truly understand the palindrome DP table. Unlike Palindrome Partitioning II (minimum cuts), where you layer a second DP on top, here you only need the precomputed table plus a simple double loop. It strips the problem down to its core: can you build the table, and can you use it efficiently?

The key insight

Build an isPalin[i][j] table where each cell tells you whether s[i..j] is a palindrome. This table fills in O(n^2) time using the recurrence: a substring is a palindrome if its first and last characters match, and the inner substring (without those two characters) is also a palindrome.

Once you have the table, you try every valid pair of cut positions. The first cut goes after index i (where i ranges from 0 to n-3), and the second cut goes after index j (where j ranges from i+1 to n-2). For each pair, you check three cells: isPalin[0][i], isPalin[i+1][j], and isPalin[j+1][n-1]. If all three are true, return true. If no pair works, return false.

The solution

def check_partitioning(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True

    for i in range(0, n - 2):
        if not is_pal[0][i]:
            continue
        for j in range(i + 1, n - 1):
            if is_pal[i + 1][j] and is_pal[j + 1][n - 1]:
                return True

    return False

The code has two clean phases. First, it fills the palindrome table by iterating i from right to left and j from i to the end. This order guarantees that when you check is_pal[i+1][j-1], that cell has already been computed. The condition j - i <= 2 handles the base cases: substrings of length 1 (always palindromes) and length 2 or 3 (palindromes if the endpoints match).

Second, it searches for a valid three-way split. The outer loop picks the end of the first part. If the first part is not a palindrome, it skips immediately. The inner loop picks the end of the second part, and if both the second and third parts are palindromes, we are done.

Visual walkthrough

The walkthrough uses s = "abcbdd". After building the palindrome table, we try split points. The first valid triple we find is i=0, j=3, giving parts "a", "bcb", and "dd". All three are palindromes according to the table, so we return true without checking further.

Complexity analysis

Time: O(n^2). Building the palindrome table examines every pair (i, j) once, taking O(n^2). The double loop over split points also visits at most O(n^2) pairs, and each check is O(1). The total is O(n^2).

Space: O(n^2). The is_pal table stores a boolean for every pair of indices. You could reduce this to O(n) by only keeping two rows of the table at a time, but for n up to 2000 the full table fits easily in memory.

The building blocks

1. Palindrome DP precomputation

for i in range(n - 1, -1, -1):
    for j in range(i, n):
        if s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1]):
            is_pal[i][j] = True

This pattern appears in nearly every palindrome substring problem. The key is the fill order: i goes from bottom to top so that is_pal[i+1][j-1] is ready when you need it. The j - i <= 2 shortcut collapses the base cases (length 1, 2, and 3 substrings) into one check, keeping the code compact.

2. Two-pointer partition search

for i in range(0, n - 2):
    if not is_pal[0][i]:
        continue
    for j in range(i + 1, n - 1):
        if is_pal[i + 1][j] and is_pal[j + 1][n - 1]:
            return True

The early continue when the first part is not a palindrome is important. It prunes entire branches of the search. Without it, you still get O(n^2) worst case, but in practice the pruning helps significantly on strings where palindromic prefixes are rare. The loop bounds ensure all three parts are non-empty: i stops at n-3 (leaving room for two more characters) and j stops at n-2 (leaving room for one more character).

Edge cases

• Already a 3-character string like "abc": each part must be exactly one character, and single characters are always palindromes. Return true for any 3-character input.
• Entire string is a palindrome like "aaa" or "abacaba": you can always split a palindrome of length 3 or more into three palindromic parts (at minimum, peel off single characters from both ends).
• No valid partition exists like "abcde" where n=5: you need to check all pairs and return false when none works. The algorithm handles this naturally.
• Long runs of the same character like "aaaa...a": every substring is a palindrome, so the very first pair of split points works and the function returns early.
• Minimum length of 3: the constraints guarantee n is at least 3, so you always have room for three non-empty parts.

From understanding to recall

Reading this solution and understanding why it works is one thing. Reproducing it from memory during an interview is quite different. Can you write the palindrome table fill with the correct loop direction? Do you remember why j - i <= 2 replaces separate base cases? Can you set the loop bounds for the two split points without off-by-one errors?

Spaced repetition turns understanding into recall. You revisit the palindrome DP precomputation and the partition search at increasing intervals, each time writing them from scratch. After a few rounds, the fill order, the recurrence, and the loop bounds become second nature. The palindrome DP table is one of roughly 60 reusable building blocks that CodeBricks helps you internalize through deliberate, spaced practice.

Related posts

• Palindrome Partitioning - The backtracking version that finds all palindrome partitions
• Palindrome Partitioning II - Minimum cuts for palindrome partitioning using DP
• Longest Palindromic Substring - The foundational palindrome DP problem

CodeBricks organizes problems like this into pattern families so you can see the connections between related problems. When you drill the palindrome DP building block, you are simultaneously preparing for this problem, its partitioning siblings, and every other problem that relies on substring palindrome queries.