# Palindrome Partitioning IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/palindrome-partitioning-iv)
Canonical: https://scaleengineer.com/dsa/problems/palindrome-partitioning-iv
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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
## 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.
**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.
**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).
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Dynamic Programming Precomputation
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Initialize an `n x n` boolean DP table `isPal`.
- Fill the `isPal` table to precompute all palindromic substrings. This can be done by iterating through all substring lengths and start positions.
  - Iterate `len` from 1 to `n`.
  - Iterate `i` from 0 to `n - len`.
  - Let `j = i + len - 1`.
  - The substring `s[i...j]` is a palindrome if its outer characters `s[i]` and `s[j]` are the same, and the inner substring `s[i+1...j-1]` is also a palindrome. The base cases are substrings of length 1 and 2.
- After the table is filled, iterate through all possible split points.
- Iterate through the first split point `i` from `1` to `n-2`.
- Inside, iterate through the second split point `j` from `i+1` to `n-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]`, and `isPal[j][n-1]`.
- If all three are `true`, return `true`.
- If the loops complete, no such partition exists, so return `false`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
# 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" ))
```

### CPP

```cpp
// 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 ; } };
```