2781

2781. Length of the Longest Valid Substring (Hard)

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.

Companies: Amazon

Related Topics:
Array, Hash Table, String, Sliding Window

Solution 1. Trie

// OJ: https://leetcode.com/problems/length-of-the-longest-valid-substring
// Author: github.com/lzl124631x
// Time: O(F + NK) where K is the maximum length of F[i]
// Space: O(F)
struct TrieNode {
    TrieNode *next[26] = {};
    bool end = false;
};
class Solution {
    void addWord(TrieNode *node, string &s) {
        for (int i = s.size() - 1; i >= 0; --i) {
            if (!node->next[s[i] - 'a']) node->next[s[i] - 'a'] = new TrieNode();
            node = node->next[s[i] - 'a'];
        }
        node->end = true;
    }
public:
    int longestValidSubstring(string s, vector<string>& F) {
        TrieNode root;
        for (auto &f : F) addWord(&root, f);
        int left = 0, ans = 0, N = s.size();
        for (int i = 0; i < N; ++i) {
            int j = i;
            bool found = false;
            auto node = &root;
            for (; j >= 0 && node->next[s[j] - 'a']; --j) { // find if there is some banned words ending at s[i]
                node = node->next[s[j] - 'a'];
                if (found = node->end) break;
            }
            if (found) left = max(left, j + 1); // If found, update the left bound
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};

Solution 2.

We use unordered_set instead of Trie to check forbidden words.

// OJ: https://leetcode.com/problems/length-of-the-longest-valid-substring
// Author: github.com/lzl124631x
// Time: O(F + NK)
// Space: O(F)
class Solution {
public:
    int longestValidSubstring(string s, vector<string>& forbidden) {
        unordered_set<string> F(begin(forbidden), end(forbidden));
        int left = 0, ans = 0, N = s.size();
        for (int i = 0; i < N; ++i) {
            int j = 0;
            for (; j < 10 && i - j >= 0; ++j) {
                if (F.count(s.substr(i - j, j + 1))) break;
            }
            if (j < 10) left = max(left, i - j + 1);
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};