2707. Extra Characters in a String

Practice Extra Characters in a String for free on NudgeCode: Medium, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Pick non-overlapping substrings of s that are words in dictionary. Every character not covered by a chosen word is extra. Return the smallest possible number of extra characters.

Example

s = "leetscode", dictionary = ["leet","code","leetcode"]  ->  1   ("leet" + "s" + "code")
s = "sayhelloworld", dictionary = ["hello","world"]      ->  3   ("say" is extra)

Constraints

• 1 <= s.length <= 50
• 1 <= dictionary.length <= 50
• 1 <= dictionary[i].length <= 50
• All strings are lowercase English letters; words in dictionary are distinct