# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/2707.-extra-characters-in-a-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.