Maximum number of non overlapping palindrome substrings

Two Pointers String Dynamic Programming Greedy

43.3% acceptance

Feb 25, 2026

502

You are given a string s and a positive integer k. Select a set of non-overlapping substrings from the string s that satisfy the following conditions: The length of each substring is at least k. Each substring is a palindrome. Return the maximum number of substrings in an optimal selection.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_palindromes(s: String, k: i32) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    let k = k as usize;

    // For each center, compute the earliest-ending palindrome of length >= k.
    // The minimal valid palindrome centered at c uses length min_k (matching parity).
    let mut events: Vec<(usize, usize)> = Vec::new(); // (start, end) inclusive

    for c in 0..n {
      // Odd palindromes centered at c
      let mut lo = c as i64 - 1;
      let mut hi = c as i64 + 1;
      while lo >= 0 && hi < n as i64 && s[lo as usize] == s[hi as usize] {
        lo -= 1;
        hi += 1;
      }
      // Max odd palindrome length = hi - lo - 1
      let odd_len = (hi - lo - 1) as usize;
      let min_odd = if k % 2 == 1 { k } else { k + 1 };
      if odd_len >= min_odd {
        let half = (min_odd - 1) / 2;
        events.push((c - half, c + half));
      }

      // Even palindromes centered between c and c+1
      if c + 1 < n {
        let mut lo = c as i64;
        let mut hi = c as i64 + 1;
        while lo >= 0 && hi < n as i64 && s[lo as usize] == s[hi as usize] {
          lo -= 1;
          hi += 1;
        }
        let even_len = (hi - lo - 1) as usize;
        let min_even = if k % 2 == 0 { k } else { k + 1 };
        if even_len >= min_even {
          let half = min_even / 2;
          events.push((c + 1 - half, c + half));
        }
      }
    }

    // Sort by end position for greedy
    events.sort_by_key(|&(_, e)| e);

    let mut count = 0;
    let mut pos = 0usize;
    for (start, end) in events {
      if start >= pos {
        count += 1;
        pos = end + 1;
      }
    }
    count
  }
}