Palindrome Partitioning IV

HARD

Description

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 <= 2000
s consists only of lowercase English letters.

Approaches

Checkout 2 different approaches to solve Palindrome Partitioning IV. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 i from 1 to n-2. This i represents the first split point (exclusive index).
Inside this loop, iterate with a variable j from i+1 to n-1. This j represents 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], and s[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 = start and right = end.
While left < right, compare s.charAt(left) and s.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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Palindrome Partitioning IV. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Palindrome Partitioning IV

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

tcs |