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).
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; }}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.