Palindrome Partitioning IV
HardPrompt
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.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to try every possible way to split the string into three non-empty parts and check if each part is a palindrome. We can use two nested loops to define the two split points.
Algorithm
- Get the length of the string,
n. - Iterate with a variable
ifrom1ton-2. Thisirepresents the first split point (exclusive index). - Inside this loop, iterate with a variable
jfromi+1ton-1. Thisjrepresents the second split point (exclusive index). - For each
(i, j)pair, we have three substrings defined by the indices:s[0...i-1],s[i...j-1], ands[j...n-1]. - Check if each of these three substrings is a palindrome using a helper function.
- If all three are palindromes, we have found a valid partition, so we return
true. - If the loops complete without finding any such partition, it means no solution exists. Return
false.
Helper function isPalindrome(s, start, end):
- This function checks if the substring
s[start...end]is a palindrome. - Use two pointers,
left = startandright = end. - While
left < right, compares.charAt(left)ands.charAt(right). - If they are not equal at any point, return
false. - If the loop finishes, it means the substring is a palindrome, so return
true.
Walkthrough
We need to find two indices, i and j, to split the string s into three substrings. For these three substrings to be non-empty, the split points must satisfy 1 <= i < j < s.length(). The algorithm iterates through all possible pairs of (i, j). The outer loop iterates i from 1 to s.length() - 2. The inner loop iterates j from i + 1 to s.length() - 1. These ranges ensure that all three resulting substrings are non-empty.
For each pair of (i, j), we check if each of the three substrings is a palindrome. To do this, we use a helper function, isPalindrome(s, start, end), which checks if a given substring s[start...end] reads the same forwards and backward. This helper function is implemented by comparing characters from both ends of the substring towards the center.
If we find a pair (i, j) for which all three substrings are palindromes, we have found a valid partition, and we can immediately return true. If the loops complete without finding any such pair, it means no such partition exists, so we return false.
class Solution { private boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) { return false; } start++; end--; } return true; } public boolean checkPartitioning(String s) { int n = s.length(); for (int i = 1; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Check partitions s[0...i-1], s[i...j-1], s[j...n-1] if (isPalindrome(s, 0, i - 1) && isPalindrome(s, i, j - 1) && isPalindrome(s, j, n - 1)) { return true; } } } return false; }}Complexity
Time
O(n^3), where n is the length of the string. There are O(n^2) possible pairs of split points. For each pair, checking if the three substrings are palindromes takes O(n) time in total, as the sum of their lengths is n.
Space
O(1) auxiliary space. We only use a few variables to keep track of indices. The palindrome check is done in-place without allocating new strings.
Trade-offs
Pros
Simple to understand and implement.
Uses minimal extra space.
Cons
Highly inefficient due to repeated palindrome checks for the same substrings.
Will likely result in a 'Time Limit Exceeded' (TLE) error for larger inputs as specified in the constraints (n <= 2000).
This approach improves upon the brute-force method by avoiding redundant palindrome checks. We can precompute whether any substring s[i...j] is a palindrome and store the results in a 2D boolean table. This allows us to check for palindromes in constant time during the main search.
Algorithm
- Initialize an
n x nboolean DP tableisPal. - Fill the
isPaltable to precompute all palindromic substrings. This can be done by iterating through all substring lengths and start positions.- Iterate
lenfrom 1 ton. - Iterate
ifrom 0 ton - len. - Let
j = i + len - 1. - The substring
s[i...j]is a palindrome if its outer characterss[i]ands[j]are the same, and the inner substrings[i+1...j-1]is also a palindrome. The base cases are substrings of length 1 and 2.
- Iterate
- After the table is filled, iterate through all possible split points.
- Iterate through the first split point
ifrom1ton-2. - Inside, iterate through the second split point
jfromi+1ton-1. - For each pair
(i, j), check if the three parts are palindromes using the precomputed table in O(1) time:isPal[0][i-1],isPal[i][j-1], andisPal[j][n-1]. - If all three are
true, returntrue. - If the loops complete, no such partition exists, so return
false.
Walkthrough
The core idea is to use dynamic programming to efficiently answer the query "is the substring s[i...j] a palindrome?". We create a 2D DP table, let's call it isPal, of size n x n, where isPal[i][j] is true if the substring from index i to j (inclusive) is a palindrome, and false otherwise.
This table can be filled in O(n^2) time. We can iterate through substrings of increasing length. A substring s[i...j] is a palindrome if s.charAt(i) == s.charAt(j) and the inner substring s[i+1...j-1] is also a palindrome (isPal[i+1][j-1]). Base cases are single characters (always palindromes) and two-character substrings.
After populating the isPal table, we can solve the main problem. We need to find two split points, i and j, that divide the string s into three non-empty palindromic substrings: s[0...i-1], s[i...j-1], and s[j...n-1].
We iterate through all valid pairs of split points (i, j). The first split point i can range from 1 to n-2. The second split point j must be after i, so it ranges from i+1 to n-1. For each pair, we check if the three substrings are palindromes using our precomputed isPal table, which is now an O(1) lookup.
If isPal[0][i-1], isPal[i][j-1], and isPal[j][n-1] are all true for any pair (i, j), we have found a valid partition and return true. If we exhaust all pairs, we return false.
class Solution { public boolean checkPartitioning(String s) { int n = s.length(); boolean[][] isPal = new boolean[n][n]; // Precompute palindrome substrings using DP for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { if (j - i <= 2) { // Substrings of length 1, 2, or 3 isPal[i][j] = true; } else { isPal[i][j] = isPal[i + 1][j - 1]; } } } } // Iterate through all possible split points for (int i = 1; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // Check partitions s[0...i-1], s[i...j-1], s[j...n-1] if (isPal[0][i - 1] && isPal[i][j - 1] && isPal[j][n - 1]) { return true; } } } return false; }}Complexity
Time
O(n^2), where n is the length of the string. Populating the DP table takes O(n^2) time. The subsequent search for the three partitions also takes O(n^2) time, as it involves two nested loops with an O(1) check inside.
Space
O(n^2), to store the n x n DP table for all palindrome substrings.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Efficient enough to pass within the time limits for the given constraints.
The precomputed table is a standard technique for many palindrome problems.
Cons
Requires O(n^2) extra space to store the DP table, which might be a concern for very large n, although it's acceptable for the given constraints.
Solutions
Solution
class Solution {public boolean checkPartitioning(String s) { int length = s.length(); boolean[][] isPalindrome = new boolean[length][length]; for (int i = 0; i < length; i++) isPalindrome[i][i] = true; for (int i = 1; i < length; i++) isPalindrome[i - 1][i] = s.charAt(i - 1) == s.charAt(i); for (int i = length - 3; i >= 0; i--) { for (int j = i + 2; j < length; j++) isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j); } int maxFirst = length - 3, maxSecond = length - 2; for (int i = 0; i <= maxFirst; i++) { if (isPalindrome[0][i]) { for (int j = i + 1; j <= maxSecond; j++) { if (isPalindrome[i + 1][j] && isPalindrome[j + 1][length - 1]) return true; } } } return false; /* also working, but a little lower efficiency for (int i = 0; i <= maxFirst; i++) { for (int j = i + 1; j <= maxSecond; j++) { if (isPalindrome[0][i] && isPalindrome[i + 1][j] && isPalindrome[j + 1][length - 1]) return true; } } */ }}############class Solution {public boolean checkPartitioning(String s) { int n = s.length(); boolean[][] g = new boolean[n][n]; for (var e : g) { Arrays.fill(e, true); } for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { g[i][j] = s.charAt(i) == s.charAt(j) && (i + 1 == j || g[i + 1][j - 1]); } } for (int i = 0; i < n - 2; ++i) { for (int j = i + 1; j < n - 1; ++j) { if (g[0][i] && g[i + 1][j] && g[j + 1][n - 1]) { return true; } } } return false; }}# 1745. Palindrome Partitioning IV # https://leetcode.com/problems/palindrome-partitioning-iv/ class Solution (): def checkPartitioning ( self , s ): n = len ( s ) dp = [[ False ] * n for _ in range ( n )] for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i , n ): if s [ i ] == s [ j ]: # j-i<=2: # case-1: j-i==0, single char itself # case-12: j-i==1, e.g. 'aa' # case-1: j-i==j, e.g. 'aba' dp [ i ][ j ] = ( j - i <= 2 ) or dp [ i + 1 ][ j - 1 ] return any ( dp [ 0 ][ i - 1 ] and dp [ i ][ j - 1 ] and dp [ j ][ n - 1 ] for i in range ( 1 , n - 1 ) for j in range ( i + 1 , n )) # below is 2nd solution from typing import List class Solution : def checkPartitioning ( self , s : str ) -> bool : isPalindrome = [ [ False ] * len ( s ) for i in range ( len ( s ))] for i in range ( len ( s )): isPalindrome [ i ][ i ] = True for i in range ( 1 , len ( s )): isPalindrome [ i - 1 ][ i ] = s [ i - 1 ] == s [ i ] for i in range ( len ( s ) - 3 , - 1 , - 1 ): for j in range ( i + 2 , len ( s ), 1 ): isPalindrome [ i ][ j ] = ( s [ i ] == s [ j ] and isPalindrome [ i + 1 ][ j - 1 ]) for i in range ( len ( s ) - 2 ): for j in range ( len ( s ) - 1 ): if isPalindrome [ 0 ][ i ] and isPalindrome [ i + 1 ][ j ] and isPalindrome [ j + 1 ][ len ( s ) - 1 ]: return True return False if __name__ == "__main__" : print ( Solution (). checkPartitioning ( "abcbdd" ))// OJ: https://leetcode.com/problems/palindrome-partitioning-iv/ // Time: O(N^2) // Space: O(N^2) class Solution { public: bool checkPartitioning ( string s ) { unsigned N = s . size (), h [ 2001 ][ 2001 ] = {}, rh [ 2001 ][ 2001 ] = {}, d = 16777619 ; for ( int i = 0 ; i < N ; ++ i ) { int hash = 0 ; for ( int j = i ; j < N ; ++ j ) { hash = hash * d + s [ j ] - 'a' ; h [ i ][ j ] = hash ; } } reverse ( begin ( s ), end ( s )); for ( int i = 0 ; i < N ; ++ i ) { int hash = 0 ; for ( int j = i ; j < N ; ++ j ) { hash = hash * d + s [ j ] - 'a' ; rh [ N - j - 1 ][ N - i - 1 ] = hash ; } } for ( int i = 0 ; i < N ; ++ i ) { // first part [0,i] if ( h [ 0 ][ i ] != rh [ 0 ][ i ]) continue ; for ( int j = i + 1 ; j < N - 1 ; ++ j ) { // second part [i+1,j], last part [j+1,N-1] if ( h [ i + 1 ][ j ] == rh [ i + 1 ][ j ] && h [ j + 1 ][ N - 1 ] == rh [ j + 1 ][ N - 1 ]) return true ; } } return false ; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.