Problem

Given a string s, return true if it is possible to split the string s _into threenon-empty palindromic substrings. Otherwise, return _false.​​​​​

A string is said to be palindrome if it the same string when reversed.

Examples

Example 1

1
2
3

Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.

Example 2

1
2
3

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.

Solution

Method 1 – Dynamic Programming for Palindrome Check

Intuition

To split the string into three non-empty palindromic substrings, we can try all possible pairs of split points and check if all three resulting substrings are palindromes. Precomputing all palindromic substrings with DP allows fast checking.

Approach

  1. Precompute a DP table isPal[i][j] indicating if s[i:j+1] is a palindrome.
  2. For all i from 1 to n-2 and j from i+1 to n-1, check if s[0:i], s[i:j], and s[j:n] are all palindromes.
  3. If such a split exists, return true; otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for (int i = n-1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1]))
                    isPal[i][j] = true;
            }
        }
        for (int i = 1; i < n-1; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (isPal[0][i-1] && isPal[i][j-1] && isPal[j][n-1])
                    return true;
            }
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func checkPartitioning(s string) bool {
    n := len(s)
    isPal := make([][]bool, n)
    for i := range isPal {
        isPal[i] = make([]bool, n)
    }
    for i := n-1; i >= 0; i-- {
        for j := i; j < n; j++ {
            if s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1]) {
                isPal[i][j] = true
            }
        }
    }
    for i := 1; i < n-1; i++ {
        for j := i+1; j < n; j++ {
            if isPal[0][i-1] && isPal[i][j-1] && isPal[j][n-1] {
                return true
            }
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j-i < 2 || isPal[i+1][j-1]))
                    isPal[i][j] = true;
            }
        }
        for (int i = 1; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (isPal[0][i-1] && isPal[i][j-1] && isPal[j][n-1])
                    return true;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun checkPartitioning(s: String): Boolean {
        val n = s.length
        val isPal = Array(n) { BooleanArray(n) }
        for (i in n-1 downTo 0) {
            for (j in i until n) {
                if (s[i] == s[j] && (j-i < 2 || isPal[i+1][j-1]))
                    isPal[i][j] = true
            }
        }
        for (i in 1 until n-1) {
            for (j in i+1 until n) {
                if (isPal[0][i-1] && isPal[i][j-1] && isPal[j][n-1])
                    return true
            }
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        is_pal = [[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] and (j-i < 2 or is_pal[i+1][j-1]):
                    is_pal[i][j] = True
        for i in range(1, n-1):
            for j in range(i+1, n):
                if is_pal[0][i-1] and is_pal[i][j-1] and is_pal[j][n-1]:
                    return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn check_partitioning(s: String) -> bool {
        let n = s.len();
        let s = s.as_bytes();
        let mut is_pal = vec![vec![false; n]; n];
        for i in (0..n).rev() {
            for j in i..n {
                if s[i] == s[j] && (j-i < 2 || is_pal[i+1][j-1]) {
                    is_pal[i][j] = true;
                }
            }
        }
        for i in 1..n-1 {
            for j in i+1..n {
                if is_pal[0][i-1] && is_pal[i][j-1] && is_pal[j][n-1] {
                    return true;
                }
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    checkPartitioning(s: string): boolean {
        const n = s.length;
        const isPal: boolean[][] = Array.from({length: n}, () => Array(n).fill(false));
        for (let i = n-1; i >= 0; i--) {
            for (let j = i; j < n; j++) {
                if (s[i] === s[j] && (j-i < 2 || isPal[i+1][j-1]))
                    isPal[i][j] = true;
            }
        }
        for (let i = 1; i < n-1; i++) {
            for (let j = i+1; j < n; j++) {
                if (isPal[0][i-1] && isPal[i][j-1] && isPal[j][n-1])
                    return true;
            }
        }
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of s. Precomputing all palindromic substrings and checking all split points is quadratic.
  • 🧺 Space complexity: O(n^2), for the DP table.