# LC 2707. Extra Characters in a String

### [Problem link](https://leetcode.com/problems/extra-characters-in-a-string/)

###### tags: `leedcode` `python` `medium`

You are given a **0-indexed** string <code>s</code> and a dictionary of words <code>dictionary</code>. You have to break <code>s</code> into one or more **non-overlapping** substrings such that each substring is present in <code>dictionary</code>. There may be some **extra characters** in <code>s</code> which are not present in any of the substrings.

Return the **minimum** number of extra characters left over if you break up <code>s</code> optimally.

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

**Constraints:**

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

## Solution 1 - DP

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        dp = [0] * (len(s) + 1)

        for i in range(1, len(s)+1):
            dp[i] = dp[i - 1]
            for d in dictionary:
                if i >= len(d) and s[i-len(d):i] == d:
                    dp[i] = max(dp[i], dp[i-len(d)]+len(d))
        
        return len(s) - dp[-1]

>### Complexity
>n = s.length
>m = dictionary.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(n) |

## Note
front to back.