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 <= 2000s consists only of lowercase English letters
Hints for Palindrome Partitioning IV
Hint 1
There are only
O(n^2)ways to choose the two cut points. The problem is checking three palindromes per choice fast.Hint 2
Precompute
pal[i][j]— whethers[i..j]is a palindrome — withpal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]), fillingifrom right to left.Hint 3
Then try every first cut
i(withs[0..i-1]a palindrome) and second cutj, and checkpal[i][j]andpal[j+1][n-1]inO(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
- Fill
pal[i][j]forifromn - 1down to 0 andjfromiup:pal[i][j]is true whens[i] == s[j]and eitherj - i < 2orpal[i+1][j-1]. - For every
iin1..n-2withpal[0][i-1]true, and everyjini..n-2: ifpal[i][j]andpal[j+1][n-1], returntrue. - 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 rowi + 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 FalseJava
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