Extra Characters in a String

Define dp[i] as the minimum number of extra characters needed to cover the prefix s[0..i). Initialize dp[0] to zero. For each end position i, first set dp[i] to dp[i-1] plus one, meaning s[i-1] is left unmatched. Then examine every start j before i; if s[j..i) is a dictionary word, update dp[i] with dp[j]. This is correct because an optimal segmentation of the prefix either leaves the last character extra or ends with one valid word, and both cases have already solved prefixes. A hash set gives expected O(1) word membership, though substring construction costs depend on the language; a trie can avoid repeated substring allocation for large inputs. Test an empty string, no matching words, overlapping word choices, and words sharing prefixes. The straightforward formulation is O(n squared) time and O(n) space, excluding dictionary storage; bounds can improve with maximum word length.