Palindrome partitioning iv

String Dynamic Programming

45.2% acceptance

Feb 25, 2026

964

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 a palindrome if it reads the same forward and backward.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn check_partitioning(s: String) -> bool {
    let s = s.as_bytes();
    let n = s.len();
    // palindrome[i][j] = true if s[i..=j] is palindrome
    let mut is_pal = vec![vec![false; n]; n];
    for i in 0..n { is_pal[i][i] = true; }
    for i in 0..n-1 { is_pal[i][i+1] = s[i] == s[i+1]; }
    for len in 3..=n {
      for i in 0..=n-len {
        let j = i + len - 1;
        is_pal[i][j] = s[i] == s[j] && is_pal[i+1][j-1];
      }
    }
    // Check all split points: part1=s[0..i-1], part2=s[i..j-1], part3=s[j..n-1]
    // i >= 1, j >= i+1, j <= n-1
    for i in 1..n {
      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
  }
}