#2707

Extra Characters in a String

specialist · 755 · lc medium +31 · verified · 57.3% accepted · 2,629 likes · top 53%

Description

You are given a 0-indexed string s and a dictionary of words. Partition s into non-overlapping substrings, each present in dictionary, minimizing the characters that do not belong to any matched substring. Return the minimum number of such leftover characters.

Example 1:

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

Output: 1

Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

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

Output: 3

Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

Code

1

2

3

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int: