最长合法子字符串的长度

标签: 数组 哈希表 字符串 滑动窗口

难度: Hard

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

Submission

运行时间: 545 ms

内存: 32.1 MB

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        visited = set(forbidden)
        lens =sorted(set(len(f) for f in forbidden))
        n = len(word)
        ans = 0
        r = n

        for l in range(n-1,-1,-1):
            for length in lens:
                if l + length > r:
                    break
                if word[l:l+length] in visited:
                    r = l+length - 1
                    break 
            ans = max(ans, r-l)
        
        return ans

Explain

该题解采用了一种从右至左遍历单词的方法，同时使用了一个集合来存储禁止的单词，以及一个列表来存储所有禁止单词的长度。在每个左端点l从右向左移动的过程中，尝试检查从当前位置l开始的各种长度的子字符串是否在禁止集合中。如果找到了匹配的禁止子字符串，就更新右端点r为当前子字符串的结束位置前一个位置。这样可以保证从位置l到r的子字符串是合法的，从而更新最长合法子字符串的长度。这种方法有效地避免了对每个可能的子字符串重复检查，而是通过动态调整右端点来快速排除非法的子字符串。

时间复杂度: O(n * maxLen)

空间复杂度: O(f + l)

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        visited = set(forbidden)  # 将禁止单词存入集合中以便快速查找
        lens = sorted(set(len(f) for f in forbidden))  # 获取所有禁止单词的长度并排序
        n = len(word)  # 单词的总长度
        ans = 0  # 最长合法子字符串的长度
        r = n  # 初始化右边界为字符串末尾

        for l in range(n-1, -1, -1):  # 从右向左遍历每个可能的起始位置
            for length in lens:  # 遍历每个禁止单词的长度
                if l + length > r:  # 如果当前长度超出了右边界，则终止此循环
                    break
                if word[l:l+length] in visited:  # 如果当前子字符串是禁止的
                    r = l + length - 1  # 更新右边界
                    break
            ans = max(ans, r - l)  # 更新最长合法子字符串的长度

        return ans  # 返回最长合法子字符串的长度

Explore

从右至左遍历字符串允许算法在发现禁止子字符串时即时调整右边界。这种方法可以从当前位置向左扩展合法子字符串的长度，一旦找到禁止的子字符串，就可以立即更新右边界，避免进一步的无效检查，并快速确定从当前左端点到新的右边界的合法子字符串长度。如果从左至右遍历，每次遇到禁止子字符串都需要重新评估右边界，这可能会增加复杂性和计算量。

排序禁止单词的长度可以使得在检查子字符串时更加高效。从最短到最长的顺序检查可以在发现禁止子字符串的最早时刻终止进一步的检查，减少不必要的比较。此外，这种排序还有助于在遍历过程中更快地决定何时停止检查更长的子字符串，尤其是当当前起点加上禁止单词的长度超过了当前的右边界时。

在算法执行过程中，变量`r`用于表示当前识别的合法子字符串的最远右边界。当从右至左遍历时，如果在位置`l`发现一个禁止的子字符串，算法会将`r`更新为该禁止子字符串结束位置的前一个位置（即`l + length - 1`），这样可以确保从位置`l`到`r`的字符串是合法的。每次更新`r`后，算法会根据当前`l`和新的`r`重新计算并更新最长合法子字符串的长度。

算法通过将所有禁止单词存储在一个集合中来处理这种情况。这意味着不管禁止单词重复多少次或有多少个禁止单词具有相同的长度，集合中每个独特的子字符串都只存储一次。在遍历过程中，算法检查从当前位置开始的特定长度的子字符串是否存在于禁止集合中。因此，即便多个禁止单词有相同的长度，算法都能有效地识别并处理这些禁止的子字符串。