Palindrome Partitioning IV solution and explanation
TCS
6 more videos on this problem
LeetCode 1745. Palindrome Partitioning IVHappy Coding · 10:09 · 1K views
花花酱 LeetCode 1745. Palindrome Partitioning IV - 刷题找工作 EP381Hua Hua · 10:44 · 1K views
1745. Palindrome Partitioning IV (Leetcode Hard)Programming Live with Larry · 51:52 · 427 views
【每日一题】1745. Palindrome Partitioning IV, 2/1/2021Huifeng Guan · 12:31 · 275 views
Leetcode 1745. Palindrome Partitioning IVAlgorithms for Big Bucks · 8:16 · 118 views
Leetcode 1745. Palindrome Partitioning IVFearless Learner · 5:39 · 65 views
LeetCode Hard 1745 Palindrome Partitioning IVrobzingcod · 7:37 · 22 views
The problem
Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.
A string is said to be palindrome if it the same string when reversed.
Example 1:
Input: s = "abcbdd" Output: true Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.
Example 2:
Input: s = "bcbddxy" Output: false Explanation: s cannot be split into 3 palindromes.
Constraints:
3 <= s.length <= 2000s consists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string s. The task is to determine whether it can be split into exactly three non-empty substrings such that each substring is a palindrome. The challenge is efficiently checking many possible split points while verifying palindrome ranges.
Approach 1: Dynamic Programming Precomputation (O(n²) time, O(n²) space)
This method builds a 2D boolean table dp[i][j] that indicates whether the substring s[i..j] is a palindrome. Fill the table using the classic recurrence: characters at both ends must match and the inner substring must also be a palindrome. After precomputing all palindrome ranges, iterate over two cut positions i and j. The string is valid if s[0..i], s[i+1..j], and s[j+1..n-1] are all palindromes according to the DP table. This approach works well because palindrome checks become constant-time lookups after preprocessing. It is a standard pattern when working with substring palindromes in dynamic programming problems involving string processing.
Approach 2: Center Expansion (O(n²) time, O(n²) space)
Instead of precomputing with DP transitions, this technique expands around every possible palindrome center. For each index, expand outward for both odd-length and even-length palindromes while the characters match. Each successful expansion marks a substring as palindromic in a lookup structure. After collecting all palindrome ranges, iterate over all pairs of split indices and verify whether the three resulting segments exist in the palindrome set. Center expansion is often simpler to implement than full DP because it mirrors how palindromes naturally grow around a center. It relies heavily on pointer expansion, a pattern closely related to two-pointer techniques.
Recommended for interviews: The dynamic programming approach is typically what interviewers expect. It demonstrates understanding of palindrome DP tables and substring preprocessing. Starting with a brute-force idea (checking all partitions and validating palindromes each time) shows the baseline reasoning, but optimizing with precomputed palindrome checks reduces repeated work and brings the solution to O(n²) time.
Approach 1: Dynamic Programming Approach
This approach involves using a dynamic programming table to precompute whether any substring of the string is a palindrome. Once this table is built, iterate over possible first and second cut points to check if the three resulting substrings are palindromic by referring to the precomputed table.
def checkPartitioning(s: str) -> bool:
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True # Every single character is a palindrome
for length in range(2, n + 1):
for start in range(n - length + 1):
end = start + length - 1
if s[start] == s[end]:
if length == 2:
dp[start][end] = True
else:
dp[start][end] = dp[start + 1][end - 1]
for i in range(n - 2):
for j in range(i + 1, n - 1):
if dp[0][i] and dp[i + 1][j] and dp[j + 1][n - 1]:
return True
return Falsepublic boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int length = 2; length <= n; length++) {
for (int start = 0; start <= n - length; start++) {
int end = start + length - 1;
if (s.charAt(start) == s.charAt(end)) {
if (length == 2) {
dp[start][end] = true;
} else {
dp[start][end] = dp[start + 1][end - 1];
}
}
}
}
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}The solution first initializes a dynamic programming table, dp, where dp[i][j] indicates whether the substring s[i:j+1] is a palindrome. The table is filled using the property that a substring is a palindrome if the first and last characters are equal and the inner substring is also a palindrome. The solution then iterates over possible first and second cut points to check if the resulting substrings are palindromic using the precomputed values in dp.
Time Complexity: O(n^2), where n is the length of the string, due to the nested loops over the length of the string.
Space Complexity: O(n^2) for storing the dp table.
Approach 2: Center Expansion Approach
This method involves expanding around potential centers for palindromes. For each character in the string, attempt to expand outward to find palindromes, and save these in a list. Then, iterate over possible partitions to see if a valid set of three palindromic substrings exists.
#include <iostream>
#include <vector>
using namespace std;
bool checkPartitioning(string s) {
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int center = 0; center < n; ++center) {
for (int offset = 0; center - offset >= 0 && center + offset < n; ++offset) {
if (s[center - offset] == s[center + offset])
dp[center - offset][center + offset] = true;
else
break;
}
for (int offset = 0; center - offset >= 0 && center + offset + 1 < n; ++offset) {
if (s[center - offset] == s[center + offset + 1])
dp[center - offset][center + offset + 1] = true;
else
break;
}
}
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}function checkPartitioning(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(false));
for (let center = 0; center < n; center++) {
for (let offset = 0; center - offset >= 0 && center + offset < n; offset++) {
if (s[center - offset] === s[center + offset]) {
dp[center - offset][center + offset] = true;
} else {
break;
}
}
for (let offset = 0; center - offset >= 0 && center + offset + 1 < n; offset++) {
if (s[center - offset] === s[center + offset + 1]) {
dp[center - offset][center + offset + 1] = true;
} else {
break;
}
}
}
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) {
return true;
}
}
}
return false;
}In this C++ solution, palindromes are identified by 'midpoints' and expanded outwards until palindrome conditions fail. These true/false palindrome checks allow possible substring palindromes to be verified quickly, following which potential partitions for valid pallindromes are evaluated. A nested for-loop further validates this.
Time Complexity: O(n^2), due to expanding around each possible center.
Space Complexity: O(n^2) for the palindrome truth table.
Approach 3: Dynamic Programming
We define f[i][j] to indicate whether the substring of s from the i-th character to the j-th character is a palindrome, initially f[i][j] = true.
Then we can calculate f[i][j] using the following state transition equation:
$
f[i][j] = \begin{cases}
true, & if s[i] = s[j] and (i + 1 = j or f[i + 1][j - 1]) \
false, & otherwise
\end{cases}
Since f[i][j] depends on f[i + 1][j - 1], we need to enumerate i from large to small and j from small to large, so that when calculating f[i][j], f[i + 1][j - 1] has already been calculated.
Next, we enumerate the right endpoint i of the first substring and the right endpoint j of the second substring. The left endpoint of the third substring can be enumerated in the range [j + 1, n - 1], where n is the length of the string s. If the first substring s[0..i], the second substring s[i+1..j], and the third substring s[j+1..n-1] are all palindromes, then we have found a feasible partitioning scheme and return true.
After enumerating all partitioning schemes, if no valid partitioning scheme is found, return false.
Time complexity is O(n^2), and space complexity is O(n^2). Where n is the length of the string s$.
function checkPartitioning(s: string): boolean {
const n = s.length;
const f: boolean[][] = Array.from({ length: n }, () => Array(n).fill(true));
for (let i = n - 1; i >= 0; --i) {
for (let j = i + 1; j < n; ++j) {
f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
}
}
for (let i = 0; i < n - 2; ++i) {
for (let j = i + 1; j < n - 1; ++j) {
if (f[0][i] && f[i + 1][j] && f[j + 1][n - 1]) {
return true;
}
}
}
return false;
}func checkPartitioning(s string) bool {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && (i+1 == j || f[i+1][j-1])
}
}
for i := 0; i < n-2; i++ {
for j := i + 1; j < n-1; j++ {
if f[0][i] && f[i+1][j] && f[j+1][n-1] {
return true
}
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the length of the string, due to the nested loops over the length of the string. |
| Center Expansion Approach | Time Complexity: O(n^2), due to expanding around each possible center. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Partition + Palindrome Check | O(n^3) | O(1) | Conceptual baseline. Useful for understanding the problem before optimization. |
| Dynamic Programming Precomputation | O(n^2) | O(n^2) | General solution for substring palindrome queries. Best balance of clarity and efficiency. |
| Center Expansion | O(n^2) | O(n^2) | Cleaner implementation when generating palindromes by expanding from centers. |
Frequently asked questions
Is Palindrome Partitioning IV easy or hard?
Palindrome Partitioning IV is labeled Hard because it combines substring DP with partition enumeration. The challenge is recognizing that repeated palindrome checks must be precomputed to avoid O(n^3) brute-force solutions.
Palindrome Partitioning IV Python/Java solution
Python and Java implementations typically build a boolean dp[n][n] table for palindrome checks, then iterate over two partition indices to verify three palindromic segments. The logic is identical across languages with O(n^2) preprocessing and constant-time substring validation.
How to solve Palindrome Partitioning IV in O(n^2)?
Precompute whether every substring is a palindrome using dynamic programming or center expansion. After preprocessing, iterate over two split indices i and j and verify if s[0..i], s[i+1..j], and s[j+1..n-1] are all palindromes. Each check becomes O(1), keeping the total runtime O(n^2).
What is the best approach for Palindrome Partitioning IV?
Dynamic programming with palindrome precomputation is the most common approach. Build a DP table where dp[i][j] indicates whether substring s[i..j] is a palindrome, then iterate over two partition points to check if three segments are palindromes. This runs in O(n^2) time and O(n^2) space and avoids repeated substring checks.
Is Palindrome Partitioning IV asked at Google/Amazon/Meta?
Palindrome partitioning and substring DP problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving palindrome checks, partition counts, or minimum cuts are common dynamic programming interview questions.
What data structure is used in Palindrome Partitioning IV?
Most solutions use a 2D boolean DP table to store whether substring ranges are palindromes. Some implementations use center expansion with a matrix or set of palindrome ranges. The core techniques involve string processing and dynamic programming.
What is the time complexity of Palindrome Partitioning IV?
The optimal solutions run in O(n^2) time. Both the dynamic programming approach and the center expansion technique spend O(n^2) time identifying palindromic substrings and testing possible partition points. Space complexity is typically O(n^2) for storing palindrome ranges.