Extra Characters in a String

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 substring.

Return the minimum number of extra characters left over if you break up s optimally.

Examples

Example 1:

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

Output: 1

Explanation: We can break s into "leet" + "s" + "code". There is 1 extra character "s", so we return 1.

Example 2:

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

Output: 3

Explanation: We can break s into "say" + "hello" + "world". The 3 extra characters are "say", so we return 3.

Example 3:

Input: s = "dwmodizxvvbosxxw", dictionary = ["dwmo","iz","xx","bosxx"]

Output: 5

Explanation: We can break s optimally into "dwmo" + "d" + "iz" + "x" + "v" + "v" + "bosxx" + "w". The 5 extra characters are "d", "x", "v", "v", and "w".

Constraints

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