#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)
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]
}
}