2781. Length of the Longest Valid Substring

Description

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.

 

Solutions

Solution: Sliding Window

• Time complexity: O(100n -> n)
• Space complexity: O(forbidden.length)

 

JavaScript

/**
 * @param {string} word
 * @param {string[]} forbidden
 * @return {number}
 */
const longestValidSubstring = function (word, forbidden) {
  const n = word.length;
  const forbiddenSet = new Set(forbidden);
  const maxSubLen = Math.max(...forbidden.map(text => text.length));
  let end = n - 1;
  let result = 0;

  for (let l = n - 1; l >= 0; l--) {
    const limit = Math.min(l + maxSubLen, end + 1);

    for (let index = l; index < limit; index++) {
      const substr = word.slice(l, index + 1);

      if (forbiddenSet.has(substr)) {
        end = index - 1;
        break;
      }
    }

    const len = end - l + 1;

    result = Math.max(len, result);
  }

  return result;
};