Leetcode-Hard

Leetcode-2781

Length of the Longest Valid Substring

2781. Length of the Longest Valid Substring

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^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.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

struct Node {
    Node* c[26];
    bool isEnd;
    
    Node() {
        isEnd = false;
        for (int i = 0; i < 26; ++i) {
            c[i] = nullptr;
        }
    }
};

class Solution {
public:
    int longestValidSubstring(std::string word, std::vector<std::string>& forbidden) {
        root = new Node();
        for (string& word : forbidden) {
            insert(word);
        }
        
        int n = word.length(), left = 0, max_len = 0;
        std::queue<std::pair<int, Node*>> q;
        for (int i = 0; i < n; ++i) {
            int idx = word[i] - 'a';
            int q_size = q.size();
            while (q_size--) {
                int start = q.front().first;
                Node* curr = q.front().second;
                q.pop();
                if (start < left) {
                    continue;
                }
                if (curr->c[idx] != nullptr) {
                    Node* next = curr->c[idx];
                    if (next->isEnd) {
                        left = std::max(left, start + 1);
                    }
                    else {
                        q.push({start, next});
                    }
                }
            }
            
            if (root->c[idx] != nullptr) {
                Node* next = root->c[idx];
                if (next->isEnd) {
                    left = std::max(left, i + 1);
                }
                else {
                    q.push({i, next});
                }
            }
            
            max_len = std::max(max_len, i - left + 1);
        }
        return max_len;
    }
    
private:
    void insert(std::string& word) {
        Node* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (node->c[idx] == nullptr) {
                node->c[idx] = new Node();
            }
            node = node->c[idx];
        }
        node->isEnd = true;
    }
    
    Node* root;
};

Leetcode-2781