Length of the Longest Valid Substring

Hard

#2494Time: 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`.

Patterns

Sliding Window

Data structures

Array Hash Table String

Prompt

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 <= 10⁵
word consists only of lowercase English letters.
1 <= forbidden.length <= 10⁵
1 <= forbidden[i].length <= 10
forbidden[i] consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.HashSet;2import java.util.List;3import java.util.Set;4 5class Solution {6    public int longestValidSubstring(String word, List<String> forbidden) {7        Set<String> forbiddenSet = new HashSet<>(forbidden);8        int maxForbiddenLength = 0;9        for (String s : forbidden) {10            maxForbiddenLength = Math.max(maxForbiddenLength, s.length());11        }12 13        int n = word.length();14        int maxLength = 0;15        int left = 0;16 17        for (int right = 0; right < n; right++) {18            // Check for forbidden substrings ending at 'right'19            for (int k = right; k >= left && k > right - maxForbiddenLength; k--) {20                String sub = word.substring(k, right + 1);21                if (forbiddenSet.contains(sub)) {22                    // If word[k..right] is forbidden, the valid substring must start after k.23                    left = k + 1;24                    // Found the longest forbidden suffix, no need to check shorter ones from this point.25                    break; 26                }27            }28            maxLength = Math.max(maxLength, right - left + 1);29        }30        return maxLength;31    }32}

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.List;2 3class TrieNode {4    TrieNode[] children = new TrieNode[26];5    boolean isEndOfWord = false;6}7 8class Solution {9    public int longestValidSubstring(String word, List<String> forbidden) {10        TrieNode root = new TrieNode();11        int maxForbiddenLength = 0;12        for (String s : forbidden) {13            maxForbiddenLength = Math.max(maxForbiddenLength, s.length());14            // Insert reversed string into Trie15            TrieNode curr = root;16            for (int i = s.length() - 1; i >= 0; i--) {17                int index = s.charAt(i) - 'a';18                if (curr.children[index] == null) {19                    curr.children[index] = new TrieNode();20                }21                curr = curr.children[index];22            }23            curr.isEndOfWord = true;24        }25 26        int n = word.length();27        int maxLength = 0;28        int left = 0;29 30        for (int right = 0; right < n; right++) {31            TrieNode curr = root;32            // Check for forbidden suffixes ending at 'right'33            for (int k = right; k >= left && k > right - maxForbiddenLength; k--) {34                int index = word.charAt(k) - 'a';35                if (curr.children[index] == null) {36                    // No forbidden word has this suffix, safe to stop37                    break;38                }39                curr = curr.children[index];40                if (curr.isEndOfWord) {41                    // word[k..right] is a forbidden substring42                    left = k + 1;43                    break;44                }45            }46            maxLength = Math.max(maxLength, right - left + 1);47        }48        return maxLength;49    }50}

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int longestValidSubstring(String word, List<String> forbidden) {4    var s = new HashSet<>(forbidden);5    int ans = 0, n = word.length();6    for (int i = 0, j = 0; j < n; ++j) {7      for (int k = j; k > Math.max(j - 10, i - 1); --k) {8        if (s.contains(word.substring(k, j + 1))) {9          i = k + 1;10          break;11        }12      }13      ans = Math.max(ans, j - i + 1);14    }15    return ans;16  }17}

1class Solution {2public:3  int longestValidSubstring(string word, vector<string> &forbidden) {4    unordered_set<string> s(forbidden.begin(), forbidden.end());5    int ans = 0, n = word.size();6    for (int i = 0, j = 0; j < n; ++j) {7      for (int k = j; k > max(j - 10, i - 1); --k) {8        if (s.count(word.substr(k, j - k + 1))) {9          i = k + 1;10          break;11        }12      }13      ans = max(ans, j - i + 1);14    }15    return ans;16  }17};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem