# Length of the Longest Valid Substring
**Difficulty:** HARD
[External](https://leetcode.com/problems/length-of-the-longest-valid-substring)
Canonical: https://scaleengineer.com/dsa/problems/length-of-the-longest-valid-substring
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table, String
---
## Problem
You are given a string `word` and an array of strings `forbidden`.

A string is called **valid** if none of its substrings are present in `forbidden`.

Return _the length of the **longest valid substring** of the string_ `word`.

A **substring** is a contiguous sequence of characters in a string, possibly empty.

**Example 1:**

**Input:** word = "cbaaaabc", forbidden = ["aaa","cb"]
**Output:** 4
**Explanation:** There are 11 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" and "aabc". The length of the longest valid substring is 4. 
It can be shown that all other substrings contain either "aaa" or "cb" as a substring. 

**Example 2:**

**Input:** word = "leetcode", forbidden = ["de","le","e"]
**Output:** 4
**Explanation:** There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4.
It can be shown that all other substrings contain either "de", "le", or "e" as a substring. 

**Constraints:**

* `1 <= word.length <= 105`
* `word` consists only of lowercase English letters.
* `1 <= forbidden.length <= 105`
* `1 <= forbidden[i].length <= 10`
* `forbidden[i]` consists only of lowercase English letters.

# Approaches
## Sliding Window with HashSet
This approach uses a sliding window, defined by `left` and `right` pointers, to iterate through the string. For each position of the `right` pointer, it checks for any forbidden substrings ending at that position by looking them up in a `HashSet`. If a forbidden substring is found, the `left` pointer is advanced to ensure the window remains valid. The maximum length of such a valid window is tracked.
**Time:** O(M * K + N * K^2), where `N` is the length of `word`, `M` is the number of forbidden strings, and `K` is their maximum length. Building the set takes O(M * K). The nested loops result in O(N * K) iterations, and inside the inner loop, `substring` and `HashSet.contains` take O(K) time. · **Space:** O(M * K), where `M` is the number of forbidden strings and `K` is their maximum length. This space is used to store the `forbiddenSet`.
**Pros:** Significantly more efficient than a naive brute-force approach.; Relatively easy to understand and implement the sliding window logic.
**Cons:** The time complexity is proportional to the square of the maximum length of a forbidden word (`K^2`), which can be suboptimal if `K` were larger.; Repeatedly creating and hashing substrings within the inner loop can be computationally expensive.
### Explanation
A more efficient way to solve this problem than brute-force is to use a sliding window approach. We can maintain a window `[left, right]` that represents a potentially valid substring. We expand this window by incrementing `right`. For each new character `word[right]`, we check if its inclusion creates any forbidden substring. Any newly formed substring must end at `right`. We only need to check suffixes of `word[..right]` that are no longer than the longest forbidden word (`K`).

We first put all forbidden strings into a `HashSet` for fast lookups. Then, as we iterate `right` from `0` to `N-1`, we check substrings `word[k..right]` for `k` from `right` down to `max(left, right - K + 1)`. If `word[k..right]` is in our `forbiddenSet`, our window is invalid. To fix this, we must move the `left` pointer to `k + 1`, effectively discarding the forbidden part. We take `left = max(left, k + 1)` to handle cases where a previously found forbidden word required an even larger `left`. After these checks, the window `word[left..right]` is valid, and we update our maximum length accordingly.

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

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> forbiddenSet = new HashSet<>(forbidden);
        int maxForbiddenLength = 0;
        for (String s : forbidden) {
            maxForbiddenLength = Math.max(maxForbiddenLength, s.length());
        }

        int n = word.length();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            // Check for forbidden substrings ending at 'right'
            for (int k = right; k >= left && k > right - maxForbiddenLength; k--) {
                String sub = word.substring(k, right + 1);
                if (forbiddenSet.contains(sub)) {
                    // If word[k..right] is forbidden, the valid substring must start after k.
                    left = k + 1;
                    // Found the longest forbidden suffix, no need to check shorter ones from this point.
                    break; 
                }
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- Create a `HashSet` from the `forbidden` list for O(1) average time lookups. Also, find the maximum length of a forbidden string, let's call it `maxForbiddenLength`.
- Initialize two pointers, `left = 0` and `right = 0`, to define a sliding window `word[left..right]`. Also, initialize `maxLength = 0`.
- Iterate with the `right` pointer from `0` to the end of the `word`.
- For each `right`, check for any forbidden substring ending at this position. To do this, iterate a pointer `k` from `right` down to `left`. We can optimize this by only checking substrings up to `maxForbiddenLength`, so `k` goes from `right` down to `max(left, right - maxForbiddenLength + 1)`.
- In the inner loop, extract the substring `sub = word.substring(k, right + 1)`.
- If `sub` is found in the `forbiddenSet`, it means the current window contains a forbidden string. To make the window valid again, we must slide the `left` pointer forward. The new `left` must be at least `k + 1`. We update `left = Math.max(left, k + 1)` and can break the inner loop since we've found the longest forbidden suffix ending at `right`.
- After the inner loop finishes, the window `word[left..right]` is guaranteed to be valid. Calculate its length `right - left + 1` and update `maxLength = Math.max(maxLength, right - left + 1)`.
- After the outer loop completes, `maxLength` will hold the length of the longest valid substring.

## Optimized Sliding Window with a Trie
This optimal approach also uses a sliding window but enhances the process of checking for forbidden substrings. Instead of a HashSet, it employs a Trie (prefix tree) built from the *reversed* forbidden strings. This allows for checking all relevant suffixes ending at the current position `right` in a single, efficient backward pass, reducing the overall time complexity.
**Time:** O(M * K + N * K), where `N` is the length of `word`, `M` is the number of forbidden strings, and `K` is their maximum length. Building the Trie takes O(M * K). The main loop runs `N` times, and the inner Trie traversal takes at most O(K) time. · **Space:** O(M * K), where `M` is the number of forbidden strings and `K` is their maximum length. This space is required to build and store the Trie.
**Pros:** Optimal time complexity for the given constraints.; The Trie allows checking for all forbidden suffixes ending at a position in O(K) time, which is a significant improvement.
**Cons:** The implementation is more complex due to the need for a Trie data structure.; The space complexity for the Trie can be significant if the character set is large or strings are long, though it's fine for the given constraints.
### Explanation
This approach optimizes the sliding window technique by replacing the `HashSet` check with a more efficient Trie-based check. The key idea is to quickly determine if any suffix of the current window `word[..right]` is a forbidden string.

We can do this efficiently by building a Trie from the reversed versions of all strings in `forbidden`. By traversing the `word` backwards from the `right` pointer and simultaneously traversing this Trie, we can check for all forbidden suffixes in a single pass. The length of this backward traversal is bounded by the maximum length of a forbidden word, `K`.

As we iterate `right` from `0` to `N-1`, we start a check from `k = right` backwards. We trace the path in the Trie corresponding to the characters `word[right], word[right-1], ...`. If we ever land on a Trie node that marks the end of a (reversed) forbidden word, say at index `k`, we know that `word[k..right]` is forbidden. We then update our window's `left` pointer to `k + 1` to exclude this substring. The rest of the logic remains the same as the HashSet approach, but this check is much faster.

```java
import java.util.List;

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

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        TrieNode root = new TrieNode();
        int maxForbiddenLength = 0;
        for (String s : forbidden) {
            maxForbiddenLength = Math.max(maxForbiddenLength, s.length());
            // Insert reversed string into Trie
            TrieNode curr = root;
            for (int i = s.length() - 1; i >= 0; i--) {
                int index = s.charAt(i) - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new TrieNode();
                }
                curr = curr.children[index];
            }
            curr.isEndOfWord = true;
        }

        int n = word.length();
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            TrieNode curr = root;
            // Check for forbidden suffixes ending at 'right'
            for (int k = right; k >= left && k > right - maxForbiddenLength; k--) {
                int index = word.charAt(k) - 'a';
                if (curr.children[index] == null) {
                    // No forbidden word has this suffix, safe to stop
                    break;
                }
                curr = curr.children[index];
                if (curr.isEndOfWord) {
                    // word[k..right] is a forbidden substring
                    left = k + 1;
                    break;
                }
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- First, build a Trie data structure. For each string in `forbidden`, reverse it and insert it into the Trie. Mark the nodes that represent the end of a reversed forbidden word.
- Initialize `maxLength = 0` and a `left` pointer to `0`.
- Iterate through the `word` with a `right` pointer from `0` to `N-1`.
- For each `right`, check for forbidden suffixes by traversing the `word` backwards from `right` and simultaneously traversing the Trie from its root.
- Start a traversal from the Trie's root with a `curr` node pointer.
- Loop with a pointer `k` from `right` down to `left`. The check can be bounded by `maxForbiddenLength` for efficiency.
- In the inner loop, try to move to the next Trie node using the character `word.charAt(k)`. If the path does not exist in the Trie, it means no forbidden word has this suffix, so we can `break` the inner loop.
- If the path exists, move `curr` to the child node. If `curr` is marked as the end of a word, it signifies that `word[k..right]` is a forbidden substring. Update `left = Math.max(left, k + 1)` and `break` the inner loop.
- After the inner loop, the window `word[left..right]` is valid. Update `maxLength = Math.max(maxLength, right - left + 1)`.
- Return `maxLength` after the main loop finishes.

# Solutions
### Java

```java
class Solution {
public
  int longestValidSubstring(String word, List<String> forbidden) {
    var s = new HashSet<>(forbidden);
    int ans = 0, n = word.length();
    for (int i = 0, j = 0; j < n; ++j) {
      for (int k = j; k > Math.max(j - 10, i - 1); --k) {
        if (s.contains(word.substring(k, j + 1))) {
          i = k + 1;
          break;
        }
      }
      ans = Math.max(ans, j - i + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int longestValidSubstring(string word, vector<string> &forbidden) {
    unordered_set<string> s(forbidden.begin(), forbidden.end());
    int ans = 0, n = word.size();
    for (int i = 0, j = 0; j < n; ++j) {
      for (int k = j; k > max(j - 10, i - 1); --k) {
        if (s.count(word.substr(k, j - k + 1))) {
          i = k + 1;
          break;
        }
      }
      ans = max(ans, j - i + 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int: s = set(forbidden) ans = i = 0 for j in range(len(word)): for k in range(j, max(j - 10, i - 1), - 1): if word[k: j + 1] in s: i = k + 1 break ans = max(ans, j - i + 1) return ans

```