361. Palindrome Partitioning IV

Precompute pal[i][j] = is s[i..j] a palindrome. Then try every pair of cut points (i, j): the three pieces are s[0..i-1], s[i..j], s[j+1..n-1]. Return true the moment all three are palindromes.

Step 1 — the palindrome table

pal[i][j] is true when s[i..j] reads the same both ways. A substring is a palindrome when its ends match and the inside is already a palindrome:

pal[i][j] = (s[i] == s[j]) and (j - i < 2 or pal[i+1][j-1])

Fill it for i from n-1 down to 0 so the inner substring pal[i+1][j-1] is ready.

Step 2 — try the two cuts

Splitting into three non-empty parts means choosing two cut points. If the first part ends at index i-1 and the middle part spans s[i..j], then the pieces are:

s[0 .. i-1]   s[i .. j]   s[j+1 .. n-1]

Scan i from 1 to n-2 and j from i to n-2, and return true as soon as pal[0][i-1] and pal[i][j] and pal[j+1][n-1] all hold.

Worked example

s = "abcbdd".

Trying cuts, i = 1, j = 3 gives the pieces "a" | "bcb" | "dd":

• "a" is a palindrome ✓
• "bcb" is a palindrome ✓
• "dd" is a palindrome ✓

All three hold → return true.

Complexity

• Time: O(n^2) — building the table and scanning the cut pairs.
• Space: O(n^2) for the palindrome table.

class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        // pal[i][j] = is s[i..j] a palindrome?
        boolean[][] pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1])) {
                    pal[i][j] = true;
                }
            }
        }
        for (int i = 1; i < n - 1; i++) {
            for (int j = i; j < n - 1; j++) {
                if (pal[0][i - 1] && pal[i][j] && pal[j + 1][n - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
}