Watch 7 video solutions for Palindrome Partitioning IV, a hard level problem involving String, Dynamic Programming. This walkthrough by Happy Coding has 1,532 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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. |