Maximum deletions on a string

String Dynamic Programming Rolling Hash String Matching Hash Function

35.7% acceptance

Feb 25, 2026

521

You are given a string s consisting of only lowercase English letters. In one operation, you can: * Delete the entire string s, or Delete the first i letters of s if the first i letters of s are equal to the following i letters in s, for any i in the range 1 <= i <= s.length / 2. * For example, if s = "ababc", then in one operation, you could delete the firs t two letters of s to get "abc", since the first two letters of s and the following two letters of s are both equal to "ab". * Return the maximum number of operations needed to delete all of s.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn delete_string(s: String) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    // lcp[i][j] = length of longest common prefix of s[i..] and s[j..]
    let mut lcp = vec![vec![0usize; n + 1]; n + 1];
    for i in (0..n).rev() {
      for j in (0..n).rev() {
        if s[i] == s[j] {
          lcp[i][j] = lcp[i + 1][j + 1] + 1;
        }
      }
    }
    let mut dp = vec![1i32; n];
    for i in (0..n).rev() {
      let len = n - i;
      for j in 1..=len / 2 {
        if lcp[i][i + j] >= j {
          dp[i] = dp[i].max(1 + dp[i + j]);
        }
      }
    }
    dp[0]
  }
}