> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Extra Characters in a String Python Solution

> Tested Python solution for LeetCode 2707 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 2707, Medium. Topics: Array, Hash Table, String, Dynamic Programming, Trie. [View on LeetCode](https://leetcode.com/problems/extra-characters-in-a-string/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2707   # by problem number
lcpy gen -s extra_characters_in_a_string   # by problem name
```

## Problem

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 of the substrings.

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

### Examples

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

```
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

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/extra_characters_in_a_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/extra_characters_in_a_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2 * m)
    # Space: O(n)
    def min_extra_char(self, s: str, dictionary: list[str]) -> int:
        n = len(s)
        word_set = set(dictionary)
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + 1
            for j in range(i):
                if s[j:i] in word_set:
                    dp[i] = min(dp[i], dp[j])

        return dp[n]
```

## Complexity

| Time        | Space |
| ----------- | ----- |
| O(n^2 \* m) | O(n)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).