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

给你一个字符串 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] 只包含小写英文字母。

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

提示 1

forbidden}[i] 的长度不超过 10。

提示 2

同向双指针 。

提示 3

初始化子串左端点 left}=0，枚举子串右端点 right。

对于示例 2，只要 right}\ge 1，那么合法子串是不能包含 le 的，所以左端点 left 必须向右移，不可能再回到 0（否则就包含 le 了）。因为左端点只会向右移动，不会向左移动，这样的单调性保证了算法的效率。

当 right 右移到一个新的字母时，枚举以该字母为右端点的 forbidden}[i] 的最短长度。如果发现子串 word}[i] 到 word}[\textit{right}] 在 forbidden 中（用哈希表实现），那么更新 left}=i+1 并结束枚举，从而避免合法子串包含 forbidden 中的字符串。枚举结束后，更新答案为合法子串长度 right}-\textit{left}+1 的最大值。

[sol-Python3]

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        fb = set(forbidden)
        ans = left = 0
        for right in range(len(word)):
            for i in range(right, max(right - 10, left - 1), -1):
                if word[i: right + 1] in fb:
                    left = i + 1  # 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
                    break
            ans = max(ans, right - left + 1)
        return ans

[sol-Java]

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        var fb = new HashSet<String>();
        fb.addAll(forbidden);
        int ans = 0, left = 0, n = word.length();
        for (int right = 0; right < n; right++) {
            for (int i = right; i >= left && i > right - 10; i--) {
                if (fb.contains(word.substring(i, right + 1))) {
                    left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
                    break;
                }
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

[sol-C++]

class Solution {
public:
    int longestValidSubstring(string word, vector<string> &forbidden) {
        unordered_set<string> fb{forbidden.begin(), forbidden.end()};
        int ans = 0, left = 0, n = word.length();
        for (int right = 0; right < n; right++) {
            for (int i = right; i >= left && i > right - 10; i--) {
                if (fb.count(word.substr(i, right - i + 1))) {
                    left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
                    break;
                }
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

[sol-Go]

func longestValidSubstring(word string, forbidden []string) (ans int) {
	has := make(map[string]bool, len(forbidden))
	for _, s := range forbidden {
		has[s] = true
	}

	left := 0
	for right := range word {
		for i := right; i >= left && i > right-10; i-- {
			if has[word[i:right+1]] {
				left = i + 1 // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
				break
			}
		}
		ans = max(ans, right-left+1)
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

[sol-JavaScript]

var longestValidSubstring = function (word, forbidden) {
    let fb = new Set();
    for (const f of forbidden) fb.add(f);
    const n = word.length;
    let ans = 0, left = 0;
    for (let right = 0; right < n; right++) {
        for (let i = right; i >= left && i > right - 10; i--) {
            if (fb.has(word.substring(i, right + 1))) {
                left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i]
                break;
            }
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
};

复杂度分析

• 时间复杂度：\mathcal{O}(L+nM^2)，其中 L 为所有 forbidden}[i] 的长度之和，n 为 word 的长度，M=10 表示 forbidden}[i] 的最长长度。请注意，在哈希表中查询一个长为 M 的字符串的时间是 \mathcal{O}(M)，每次移动右指针会执行至多 M 次这样的查询。
• 空间复杂度：\mathcal{O}(L)。

相似题目

• 3. 无重复字符的最长子串