Palindrome Partitioning IV - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Code
C++
JavaScript
Complexity
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$.
Code
Python
Java
C++
Go
TypeScript
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 | ā |
Detailed 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. |
Video Solution
LeetCode 1745. Palindrome Partitioning IV ā¢ Happy Coding ā¢ 1,568 views views
Watch 6 more video solutions āFrequently Asked Questions
Is Palindrome Partitioning IV easy or hard?
Palindrome Partitioning IV Python/Java solution
How to solve Palindrome Partitioning IV in O(n^2)?
What is the best approach for Palindrome Partitioning IV?
Is Palindrome Partitioning IV asked at Google/Amazon/Meta?
What data structure is used in Palindrome Partitioning IV?
What is the time complexity of Palindrome Partitioning IV?
Ready to solve this problem?
Practice Palindrome Partitioning IV with our built-in code editor and test cases.
Practice on FleetCode