---
# System prepended metadata

title: LC 2707. Extra Characters in a String
tags: [medium, leedcode, python]

---

# 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
```python=
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.
