Palindrome Partitioning IV

Hard
1273.

Palindrome Partitioning IV

Palindrome Partitioning IV is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

Return true if the string s can be split into exactly three non-empty substrings, each of which is a palindrome (reads the same forwards and backwards). Otherwise return false.

Example 1

Input
s = "kayakmomx"
Output
true
Explanation
`kayak` + `mom` + `x`.

Example 2

Input
s = "abcde"
Output
false

Example 3

Input
s = "aaa"
Output
true
Explanation
`a` + `a` + `a`.

Constraints

  • 3 <= s.length <= 2000
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var checkPartitioning = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Palindrome Partitioning IV — Solution in Python, Java & C++

Palindrome Partitioning IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Palindrome Partitioning IV is a hard coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return true if the string s can be split into exactly three non-empty substrings, each of which is a palindrome (reads the same forwards and backwards). Otherwise return false.

Example 1

Input: s = "kayakmomx"
Output: true
Explanation: `kayak` + `mom` + `x`.

Example 2

Input: s = "abcde"
Output: false

Example 3

Input: s = "aaa"
Output: true
Explanation: `a` + `a` + `a`.

Constraints

  • 3 <= s.length <= 2000
  • s consists only of lowercase English letters

Hints for Palindrome Partitioning IV

  1. Hint 1

    There are only O(n^2) ways to choose the two cut points. The problem is checking three palindromes per choice fast.

  2. Hint 2

    Precompute pal[i][j] — whether s[i..j] is a palindrome — with pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]), filling i from right to left.

  3. Hint 3

    Then try every first cut i (with s[0..i-1] a palindrome) and second cut j, and check pal[i][j] and pal[j+1][n-1] in O(1).

How to solve Palindrome Partitioning IV

A table of which substrings are palindromes turns every candidate split into three O(1) lookups, and there are only O(n^2) splits.

Approach

  1. Fill pal[i][j] for i from n - 1 down to 0 and j from i up: pal[i][j] is true when s[i] == s[j] and either j - i < 2 or pal[i+1][j-1].
  2. For every i in 1..n-2 with pal[0][i-1] true, and every j in i..n-2: if pal[i][j] and pal[j+1][n-1], return true.
  3. Return false.

Why it works

A substring is a palindrome exactly when its end characters match and its interior is a palindrome (or it is too short to have one), which is the recurrence; filling i downwards ensures pal[i+1][j-1] is ready. The double loop enumerates every way to cut s into three non-empty parts, so the answer is found if it exists.

Complexity

  • Time — O(n^2)
  • Space — O(n^2)

Pitfalls

  • All three parts must be non-empty: the first cut is at least 1 and the second leaves at least one character.
  • Checking each candidate part directly costs O(n) per split — O(n^3) overall.
  • Fill order matters: pal[i][j] depends on row i + 1.

Reference solution

Python

def checkPartitioning(s: str) -> bool:
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        row, inner = pal[i], pal[i + 1] if i + 1 < n else None
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or inner[j - 1]):
                row[j] = True
    for i in range(1, n - 1):
        if not pal[0][i - 1]:
            continue
        for j in range(i, n - 1):
            if pal[i][j] and pal[j + 1][n - 1]:
                return True
    return False

Java

public static boolean checkPartitioning(String s) {
    int n = s.length();
    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 a = 1; a < n - 1; a++) {
        if (!pal[0][a - 1]) continue;
        for (int b = a; b < n - 1; b++) {
            if (pal[a][b] && pal[b + 1][n - 1]) return true;
        }
    }
    return false;
}

C++

bool checkPartitioning(string s) {
    int n = s.size();
    vector<vector<char>> pal(n, vector<char>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = 1;
        }
    }
    for (int a = 1; a < n - 1; a++) {
        if (!pal[0][a - 1]) continue;
        for (int b = a; b < n - 1; b++) {
            if (pal[a][b] && pal[b + 1][n - 1]) return true;
        }
    }
    return false;
}

JavaScript

var checkPartitioning = function(s) {
    var n = s.length;
    var pal = [];
    for (var r = 0; r < n; r++) pal.push(new Uint8Array(n));
    for (var i = n - 1; i >= 0; i--) {
        for (var j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1])) pal[i][j] = 1;
        }
    }
    for (var a = 1; a < n - 1; a++) {
        if (!pal[0][a - 1]) continue;
        for (var b = a; b < n - 1; b++) {
            if (pal[a][b] && pal[b + 1][n - 1]) return true;
        }
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming