Extra Characters in a String

The key idea

Read s from right to left. The fewest extra characters for the suffix starting at index i is either: keep s[i] as extra and reuse the answer for i + 1, or match a dictionary word that begins at i and jump past it for free. Take the smaller.

Problem

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.

Constraints

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] and s consists of only lowercase English letters
dictionary contains distinct words

Examples

Input: s = "leetscode", dictionary = ["leet","code","leetcode"] Output: 1

Input: s = "sayhelloworld", dictionary = ["hello","world"] Output: 3

Complexity

Time: O(n^2) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →