> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/2707.-extra-characters-in-a-string.md).

# 2707. Extra Characters in a String

## Problem Statement

<br>

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

&#x20;

**Example 1:**

<pre><code><strong>Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
</strong><strong>Output: 1
</strong><strong>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.
</strong>
</code></pre>

**Example 2:**

<pre><code><strong>Input: s = "sayhelloworld", dictionary = ["hello","world"]
</strong><strong>Output: 3
</strong><strong>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.
</strong></code></pre>

&#x20;

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

## Intuition

```
Approach:

If the string does not match, Most likely
It is the removal characters

Take that string lenght + f(index+1)
Or if matches 0 + f(index+1)
```

### Links

<https://leetcode.com/problems/extra-characters-in-a-string/description/?envType=daily-question&envId=2023-09-02>

### Video Links

<https://www.youtube.com/watch?v=LlHTq13EhMw&t=716s&ab_channel=AryanMittal>

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    unordered_map<string, bool> mp;
    vector<int> dp;
    int find_ans(string &s, int index){
        if(index == s.size())
            return 0;

        if(dp[index] != -1)
            return dp[index];

        int ans = INT_MAX;
        for(int cur=index; cur<s.size(); cur++){
            string temp = s.substr(index, cur-index+1);
            int temp_ans;

            if(!mp[temp])
                temp_ans = temp.size() + find_ans(s, cur+1);
            else
                temp_ans = find_ans(s, cur+1);

            ans=min(ans, temp_ans);
        }

        return dp[index] = ans;
    }


    int minExtraChar(string s, vector<string>& dict) {
        for(auto &it: dict)
            mp[it] = true;
        
        dp = vector<int>(s.size(),-1);

        return find_ans(s, 0);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###