Length of the Longest Valid Substring

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 thelongest valid substring of the string _word.

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

Examples

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

Solution

Method 1 – Sliding Window with Trie

Intuition

To find the longest valid substring, we need to efficiently check if any substring is forbidden. We can use a sliding window and a Trie to quickly check for forbidden substrings ending at each position.

Approach

1. Build a Trie from the forbidden words (insert each word in reverse for efficient suffix checking).
2. Use a sliding window: for each end index, try to extend the window as far left as possible without including a forbidden substring.
3. For each end index, check all suffixes up to the max forbidden word length using the Trie.
4. If a forbidden substring is found, move the left pointer to exclude it.
5. Track and return the maximum window size.

Code

C++

class Trie {
public:
    Trie* next[26] = {};
    bool is_end = false;
    void insert(const string& s) {
        Trie* node = this;
        for (char ch : s) {
            int idx = ch - 'a';
            if (!node->next[idx]) node->next[idx] = new Trie();
            node = node->next[idx];
        }
        node->is_end = true;
    }
};
class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        Trie root;
        int maxlen = 0;
        for (auto& f : forbidden) {
            string rev = f;
            reverse(rev.begin(), rev.end());
            root.insert(rev);
        }
        int n = word.size(), l = 0, ans = 0, maxf = 0;
        for (auto& f : forbidden) maxf = max(maxf, (int)f.size());
        for (int r = 0; r < n; ++r) {
            Trie* node = &root;
            for (int k = 0; k < maxf && r-k >= l; ++k) {
                int idx = word[r-k] - 'a';
                if (!node->next[idx]) break;
                node = node->next[idx];
                if (node->is_end) { l = r-k+1; break; }
            }
            ans = max(ans, r-l+1);
        }
        return ans;
    }
};

Go

type Trie struct {
    next [26]*Trie
    isEnd bool
}
func (t *Trie) insert(s string) {
    node := t
    for _, ch := range s {
        idx := ch - 'a'
        if node.next[idx] == nil {
            node.next[idx] = &Trie{}
        }
        node = node.next[idx]
    }
    node.isEnd = true
}
func longestValidSubstring(word string, forbidden []string) int {
    root := &Trie{}
    maxf := 0
    for _, f := range forbidden {
        if len(f) > maxf { maxf = len(f) }
        rev := []rune(f)
        for i, j := 0, len(rev)-1; i < j; i, j = i+1, j-1 {
            rev[i], rev[j] = rev[j], rev[i]
        }
        root.insert(string(rev))
    }
    n, l, ans := len(word), 0, 0
    for r := 0; r < n; r++ {
        node := root
        for k := 0; k < maxf && r-k >= l; k++ {
            idx := word[r-k] - 'a'
            if node.next[idx] == nil { break }
            node = node.next[idx]
            if node.isEnd { l = r-k+1; break }
        }
        if r-l+1 > ans { ans = r-l+1 }
    }
    return ans
}

Java

class Trie {
    Trie[] next = new Trie[26];
    boolean isEnd = false;
    void insert(String s) {
        Trie node = this;
        for (char ch : s.toCharArray()) {
            int idx = ch - 'a';
            if (node.next[idx] == null) node.next[idx] = new Trie();
            node = node.next[idx];
        }
        node.isEnd = true;
    }
}
class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Trie root = new Trie();
        int maxf = 0;
        for (String f : forbidden) {
            maxf = Math.max(maxf, f.length());
            StringBuilder sb = new StringBuilder(f).reverse();
            root.insert(sb.toString());
        }
        int n = word.length(), l = 0, ans = 0;
        for (int r = 0; r < n; r++) {
            Trie node = root;
            for (int k = 0; k < maxf && r-k >= l; k++) {
                int idx = word.charAt(r-k) - 'a';
                if (node.next[idx] == null) break;
                node = node.next[idx];
                if (node.isEnd) { l = r-k+1; break; }
            }
            ans = Math.max(ans, r-l+1);
        }
        return ans;
    }
}

Kotlin

class Trie {
    val next = Array<Trie?>(26) { null }
    var isEnd = false
    fun insert(s: String) {
        var node = this
        for (ch in s) {
            val idx = ch - 'a'
            if (node.next[idx] == null) node.next[idx] = Trie()
            node = node.next[idx]!!
        }
        node.isEnd = true
    }
}
class Solution {
    fun longestValidSubstring(word: String, forbidden: List<String>): Int {
        val root = Trie()
        var maxf = 0
        for (f in forbidden) {
            maxf = maxOf(maxf, f.length)
            root.insert(f.reversed())
        }
        val n = word.length
        var l = 0; var ans = 0
        for (r in 0 until n) {
            var node = root
            for (k in 0 until maxf) {
                if (r-k < l) break
                val idx = word[r-k] - 'a'
                node = node.next[idx] ?: break
                if (node.isEnd) { l = r-k+1; break }
            }
            ans = maxOf(ans, r-l+1)
        }
        return ans
    }
}

Python

class Trie:
    def __init__(self):
        self.next = {}
        self.is_end = False
    def insert(self, s: str):
        node = self
        for ch in s:
            if ch not in node.next:
                node.next[ch] = Trie()
            node = node.next[ch]
        node.is_end = True
class Solution:
    def longestValidSubstring(self, word: str, forbidden: list[str]) -> int:
        root = Trie()
        maxf = 0
        for f in forbidden:
            maxf = max(maxf, len(f))
            root.insert(f[::-1])
        n, l, ans = len(word), 0, 0
        for r in range(n):
            node = root
            for k in range(maxf):
                if r-k < l: break
                ch = word[r-k]
                if ch not in node.next: break
                node = node.next[ch]
                if node.is_end:
                    l = r-k+1
                    break
            ans = max(ans, r-l+1)
        return ans

Rust

impl Solution {
    pub fn longest_valid_substring(word: String, forbidden: Vec<String>) -> i32 {
        use std::collections::HashMap;
        struct Trie { next: HashMap<u8, Box<Trie>>, is_end: bool }
        impl Trie {
            fn new() -> Self { Trie { next: HashMap::new(), is_end: false } }
            fn insert(&mut self, s: &[u8]) {
                let mut node = self;
                for &ch in s {
                    node = node.next.entry(ch).or_insert_with(|| Box::new(Trie::new()));
                }
                node.is_end = true;
            }
        }
        let mut root = Trie::new();
        let mut maxf = 0;
        for f in &forbidden {
            maxf = maxf.max(f.len());
            let rev: Vec<u8> = f.bytes().rev().collect();
            root.insert(&rev);
        }
        let word = word.as_bytes();
        let n = word.len();
        let mut l = 0; let mut ans = 0;
        for r in 0..n {
            let mut node = &root;
            for k in 0..maxf {
                if r < k || r-k < l { break; }
                let ch = word[r-k];
                if let Some(next) = node.next.get(&ch) {
                    node = next;
                    if node.is_end { l = r-k+1; break; }
                } else { break; }
            }
            ans = ans.max(r as i32 - l as i32 + 1);
        }
        ans
    }
}

TypeScript

class Trie {
    next: Map<string, Trie> = new Map();
    isEnd = false;
    insert(s: string) {
        let node: Trie = this;
        for (const ch of s) {
            if (!node.next.has(ch)) node.next.set(ch, new Trie());
            node = node.next.get(ch)!;
        }
        node.isEnd = true;
    }
}
class Solution {
    longestValidSubstring(word: string, forbidden: string[]): number {
        const root = new Trie();
        let maxf = 0;
        for (const f of forbidden) {
            maxf = Math.max(maxf, f.length);
            root.insert([...f].reverse().join(''));
        }
        let n = word.length, l = 0, ans = 0;
        for (let r = 0; r < n; r++) {
            let node = root;
            for (let k = 0; k < maxf && r-k >= l; k++) {
                const ch = word[r-k];
                if (!node.next.has(ch)) break;
                node = node.next.get(ch)!;
                if (node.isEnd) { l = r-k+1; break; }
            }
            ans = Math.max(ans, r-l+1);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n*m), where n is the length of word and m is the total length of forbidden words (since we check up to max forbidden length for each position).
• 🧺 Space complexity: O(m), for the Trie storing all forbidden words.