# Extra Characters in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/extra-characters-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/extra-characters-in-a-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [PornHub](https://scaleengineer.com/companies/pornhub)
---
## 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._

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

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

# Approaches
## Brute-Force Recursion
This approach directly translates the problem into a recursive structure. We explore all possible ways to partition the string. At each position, we decide whether to skip the character (counting it as extra) or to match it as part of a dictionary word. This exhaustive search explores every possibility to find the minimum number of extra characters.
**Time:** O(2^n * n * k), where n is the length of `s` and k is the average length of a dictionary word. The complexity is exponential because at each character, the function can branch, leading to a number of calls that grows exponentially with `n`. The additional factors account for substring creation and dictionary lookups. · **Space:** O(n), where n is the length of the string `s`. This space is used by the recursion call stack.
**Pros:** Simple to understand and implement as it directly models the problem's decision-making process.
**Cons:** Extremely inefficient due to the massive number of redundant computations for the same subproblems.; Will lead to a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.
### Explanation
The core idea is to define a function, let's say `solve(i)`, which computes the minimum extra characters for the suffix of the string `s` starting at index `i`. To compute `solve(i)`, we consider two possibilities. First, we can treat the character `s[i]` as an extra character. In this case, the total number of extra characters will be 1 (for `s[i]`) plus the result of the subproblem for the rest of the string, which is `solve(i+1)`. Second, we can try to match a word from the dictionary that starts at index `i`. We check every substring `s[i...j]` (for `j` from `i` to `n-1`) against the dictionary. If a match is found, we've successfully covered that part of the string with zero extra characters, and we recursively call `solve(j+1)` to handle the remainder of the string. The final result for `solve(i)` is the minimum value obtained from all these possibilities. The initial call would be `solve(0)`.
### Algorithm
- Define a recursive function `solve(startIndex)` that calculates the minimum extra characters for the suffix of `s` starting from `startIndex`.
- **Base Case:** If `startIndex` reaches the end of the string (`s.length()`), it means we have processed the entire string, so we return 0.
- **Recursive Step:** For any `startIndex`, we have two main choices:
  1.  Treat the character `s[startIndex]` as an extra character. The cost for this choice is `1 + solve(startIndex + 1)`.
  2.  Try to form a word from the dictionary starting at `startIndex`. We iterate through all possible end indices `j` from `startIndex` to `s.length() - 1`. If the substring `s.substring(startIndex, j + 1)` exists in the dictionary, this is a valid move. The cost for this choice is `solve(j + 1)`, as the characters in the word are not extra.
- The function returns the minimum cost among all possible choices.

## Bottom-Up Dynamic Programming
This approach improves upon the brute-force recursion by using dynamic programming to avoid recomputing results for the same subproblems. We use a bottom-up approach, building the solution for the entire string from the solutions for its suffixes. An array `dp` is used, where `dp[i]` stores the minimum extra characters needed for the substring `s` starting at index `i`.
**Time:** O(n^3). We have two nested loops for `i` and `j`, which is `O(n^2)`. Inside the inner loop, `s.substring(i, j + 1)` takes `O(n)` time in Java, leading to a total complexity of `O(n^3)`. · **Space:** O(n + L), where `n` is the length of `s` and `L` is the total number of characters in the dictionary. `O(n)` is for the `dp` array and `O(L)` is for storing the dictionary in a `HashSet`.
**Pros:** Significantly more efficient than brute-force recursion.; Guaranteed to find the optimal solution by systematically building it up.; Passes the given constraints.
**Cons:** The time complexity of O(n^3) might be too slow for larger constraints, although it passes for this problem's specific limits.; The repeated creation of substrings inside the loops can be inefficient.
### Explanation
We define `dp[i]` as the minimum number of extra characters in the suffix `s[i..n-1]`. Our goal is to find `dp[0]`. The base case is `dp[n] = 0`, representing an empty string suffix which has zero extra characters. We compute the `dp` values iteratively, starting from the end of the string and moving backwards to the beginning. For each index `i`, we have two choices:
1.  **Skip `s[i]`**: Treat `s[i]` as an extra character. The cost is `1 + dp[i+1]`.
2.  **Form a word**: Check every substring `s[i..j]` starting at `i`. If `s[i..j]` is in the dictionary, we have the option of taking this word, and the cost would be `dp[j+1]`. 
We set `dp[i]` to the minimum value found among all these choices. To make dictionary lookups fast, we pre-process the `dictionary` into a `HashSet`.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();
        Set<String> dictSet = new HashSet<>(Arrays.asList(dictionary));
        int[] dp = new int[n + 1];
        
        for (int i = n - 1; i >= 0; i--) {
            // Option 1: Treat s[i] as an extra character
            dp[i] = 1 + dp[i + 1];
            
            // Option 2: Try to form a word starting at i
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                if (dictSet.contains(sub)) {
                    dp[i] = Math.min(dp[i], dp[j + 1]);
                }
            }
        }
        
        return dp[0];
    }
}
```
### Algorithm
- First, convert the `dictionary` array into a `HashSet` for efficient O(1) average time lookups.
- Create a DP array, `dp`, of size `n + 1`, where `n` is the length of `s`.
- `dp[i]` will store the minimum number of extra characters for the suffix `s[i...]`.
- Initialize `dp[n] = 0`, as the empty suffix has no extra characters.
- Iterate backwards from `i = n - 1` down to `0`.
- For each `i`, first assume `s[i]` is an extra character, so set `dp[i] = 1 + dp[i+1]`.
- Then, iterate with a second pointer `j` from `i` to `n - 1`. Form the substring `sub = s.substring(i, j + 1)`.
- If `sub` is present in the dictionary `HashSet`, it means we can form a word. This gives us another possible value for `dp[i]`, which is `dp[j + 1]`. We update `dp[i]` to be the minimum of its current value and `dp[j + 1]`.
- After the loops complete, `dp[0]` will hold the minimum extra characters for the entire string `s`.

## Optimal Dynamic Programming with Trie
This is the most optimal approach, which refines the dynamic programming solution. The bottleneck in the previous DP approach was the repeated scanning and substring creation to find matching dictionary words. We can optimize this by using a Trie (Prefix Tree). By pre-processing the dictionary into a Trie, we can efficiently find all dictionary words that are prefixes of `s` starting from any position `i` in a single pass.
**Time:** O(n*k + L), where `L` is the total number of characters in the dictionary, `n` is the length of `s`, and `k` is the maximum length of a word in the dictionary. `O(L)` is for building the Trie. The DP calculation takes `O(n*k)` because the outer loop runs `n` times, and the inner `j` loop runs at most `k` times (the maximum depth of the Trie). · **Space:** O(n + L), where `n` is for the `dp` array and `L` is the total number of characters in the dictionary for storing the Trie.
**Pros:** The most efficient time complexity among all approaches.; Scales well even if the length of the string `s` were larger.
**Cons:** The implementation is more complex due to the need for a Trie data structure.
### Explanation
We use the same DP state `dp[i]` as in the previous approach. However, we change how we find matching words. Instead of generating substrings and checking for their existence in a set, we build a Trie from the dictionary. When calculating `dp[i]`, we start traversing the Trie from its root using characters from `s` starting at index `i`. As we traverse with a pointer `j` from `i` to `n-1`, if the current node in the Trie marks the end of a word, we know that `s.substring(i, j+1)` is a dictionary word. This allows us to consider the option of taking this word and transitioning to the state `dp[j+1]`. This avoids the `O(n)` substring creation cost at each step of the inner loop, reducing the complexity of the DP calculation.

```java
class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    public int minExtraChar(String s, String[] dictionary) {
        int n = s.length();
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
            }
            curr.isEndOfWord = true;
        }

        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = 1 + dp[i + 1]; // Default: skip s[i]
            TrieNode curr = root;
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (curr.children[c - 'a'] == null) {
                    break; // No word in dict starts with s[i...j+1]
                }
                curr = curr.children[c - 'a'];
                if (curr.isEndOfWord) {
                    // Found a word s[i...j]
                    dp[i] = Math.min(dp[i], dp[j + 1]);
                }
            }
        }
        return dp[0];
    }
}
```
### Algorithm
- **Trie Node:** Define a `TrieNode` class, which contains an array of children (e.g., of size 26 for lowercase English letters) and a boolean flag `isEndOfWord`.
- **Build Trie:** Create a Trie data structure and insert every word from the `dictionary` into it.
- **DP Array:** Create a `dp` array of size `n + 1`, where `dp[i]` stores the minimum extra characters for the suffix `s[i...]`. Initialize `dp[n] = 0`.
- **DP Calculation:** Iterate `i` from `n - 1` down to `0`.
  - Set the default value `dp[i] = 1 + dp[i+1]` (for skipping `s[i]`)
  - Start a traversal of the Trie from its root. Iterate with a pointer `j` from `i` to `n - 1`.
  - For each character `s[j]`, try to move to the corresponding child in the Trie.
  - If at any point a path does not exist, break the inner loop, as no more words can be formed.
  - If the current `TrieNode` has `isEndOfWord` set to `true`, it means `s[i...j]` is a valid word. We then have a potential better value for `dp[i]`, which is `dp[j + 1]`. Update `dp[i] = min(dp[i], dp[j + 1])`.
- **Result:** The final answer is `dp[0]`.

# Solutions
### Java

```java
class Solution {
public
  int minExtraChar(String s, String[] dictionary) {
    Set<String> ss = new HashSet<>();
    for (String w : dictionary) {
      ss.add(w);
    }
    int n = s.length();
    int[] f = new int[n + 1];
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      f[i] = f[i - 1] + 1;
      for (int j = 0; j < i; ++j) {
        if (ss.contains(s.substring(j, i))) {
          f[i] = Math.min(f[i], f[j]);
        }
      }
    }
    return f[n];
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {string[]} dictionary * @return {number} */ var minExtraChar = function ( s , dictionary ) { const ss = new Set ( dictionary ); const n = s . length ; const f = Array ( n + 1 ). fill ( 0 ); for ( let i = 1 ; i <= n ; ++ i ) { f [ i ] = f [ i - 1 ] + 1 ; for ( let j = 0 ; j < i ; ++ j ) { if ( ss . has ( s . slice ( j , i ))) { f [ i ] = Math . min ( f [ i ], f [ j ]); } } } return f [ n ]; };
```

### Python

```python
class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int: ss = set(dictionary) n = len(s) f = [0] * (n + 1) for i in range(1, n + 1): f[i] = f[i - 1] + 1 for j in range(i): if s[j: i] in ss and f[j] < f[i]: f[i] = f[j] return f[n]

```

### CPP

```cpp
class Solution {
public:
  int minExtraChar(string s, vector<string> &dictionary) {
    unordered_set<string> ss(dictionary.begin(), dictionary.end());
    int n = s.size();
    int f[n + 1];
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
      f[i] = f[i - 1] + 1;
      for (int j = 0; j < i; ++j) {
        if (ss.count(s.substr(j, i - j))) {
          f[i] = min(f[i], f[j]);
        }
      }
    }
    return f[n];
  }
};

```