Skip to main content
Back to problems
#2707
Medium Algorithms

Extra characters in a string

Array Hash Table String Dynamic Programming Trie
57.3% acceptance
Feb 25, 2026
2627
138
You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings. Return the minimum number of extra characters left over if you break up s optimally.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs
impl Solution {
  pub fn min_extra_char(s: String, dictionary: Vec<String>) -> i32 {
    let n = s.len();
    let sb = s.as_bytes();
    let mut dp = vec![0i32; n + 1];
    for i in 1..=n {
      dp[i] = dp[i - 1] + 1;
      for w in &dictionary {
        let wl = w.len();
        if i >= wl && &sb[i - wl..i] == w.as_bytes() {
          dp[i] = dp[i].min(dp[i - wl]);
        }
      }
    }
    dp[n]
  }
}