Question

2781. 最长合法子字符串的长度

English Version

题目描述

给你一个字符串 word 和一个字符串数组 forbidden 。

如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。

请你返回字符串 word 的一个 最长合法子字符串 的长度。

子字符串 指的是一个字符串中一段连续的字符，它可以为空。

 

示例 1：

输入：word = "cbaaaabc", forbidden = ["aaa","cb"]
输出：4
解释：总共有 11 个合法子字符串："c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" 和 "aabc"。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 "aaa" ，要么包含 "cb" 。

示例 2：

输入：word = "leetcode", forbidden = ["de","le","e"]
输出：4
解释：总共有 11 个合法子字符串："l" ，"t" ，"c" ，"o" ，"d" ，"tc" ，"co" ，"od" ，"tco" ，"cod" 和 "tcod" 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 "de" ，"le" 和 "e" 之一。

 

提示：

• 1 <= word.length <= 105
• word 只包含小写英文字母。
• 1 <= forbidden.length <= 105
• 1 <= forbidden[i].length <= 10
• forbidden[i] 只包含小写英文字母。

解法

方法一：哈希表 + 双指针

我们用哈希表 $s$ 记录所有禁止的字符串，然后用双指针 $i$ 和 $j$ 遍历字符串 $word$，其中 $i$ 和 $j$ 分别表示当前合法子字符串的左右边界。

接下来，我们枚举子字符串的右端点 $j$，判断此时 $word[k..j]$ 是否合法，如果不合法，那么我们更新 $i = k + 1$。接下来更新答案 $ans = \max(ans, j - i + 1)$。

时间复杂度 $O(n \times \max(|forbidden[i]|^2) + m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别表示字符串 $word$ 和 $forbidden$ 的长度。

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

class Solution {
  public int longestValidSubstring(String word, List<String> forbidden) {
    var s = new HashSet<>(forbidden);
    int ans = 0, n = word.length();
    for (int i = 0, j = 0; j < n; ++j) {
      for (int k = j; k > Math.max(j - 10, i - 1); --k) {
        if (s.contains(word.substring(k, j + 1))) {
          i = k + 1;
          break;
        }
      }
      ans = Math.max(ans, j - i + 1);
    }
    return ans;
  }
}

class Solution {
public:
  int longestValidSubstring(string word, vector<string>& forbidden) {
    unordered_set<string> s(forbidden.begin(), forbidden.end());
    int ans = 0, n = word.size();
    for (int i = 0, j = 0; j < n; ++j) {
      for (int k = j; k > max(j - 10, i - 1); --k) {
        if (s.count(word.substr(k, j - k + 1))) {
          i = k + 1;
          break;
        }
      }
      ans = max(ans, j - i + 1);
    }
    return ans;
  }
};

func longestValidSubstring(word string, forbidden []string) (ans int) {
  s := map[string]bool{}
  for _, x := range forbidden {
    s[x] = true
  }
  n := len(word)
  for i, j := 0, 0; j < n; j++ {
    for k := j; k > max(j-10, i-1); k-- {
      if s[word[k:j+1]] {
        i = k + 1
        break
      }
    }
    ans = max(ans, j-i+1)
  }
  return
}

function longestValidSubstring(word: string, forbidden: string[]): number {
  const s: Set<string> = new Set(forbidden);
  const n = word.length;
  let ans = 0;
  for (let i = 0, j = 0; j < n; ++j) {
    for (let k = j; k > Math.max(j - 10, i - 1); --k) {
      if (s.has(word.substring(k, j + 1))) {
        i = k + 1;
        break;
      }
    }
    ans = Math.max(ans, j - i + 1);
  }
  return ans;
}