最长合法子字符串长度 - 算法详解及Python实现

首先，我们可以将 forbidden 数组转化为一个集合，方便后续判断一个字符串是否在 forbidden 中。\n\n然后，我们从字符串 word 的第一个字符开始，依次遍历每一个字符。如果当前字符与 forbidden 中的某个字符串匹配，我们就将当前字符的索引记为 end。\n\n在遍历的过程中，我们还需要维护一个变量 start 来记录合法子字符串的起始位置。如果当前字符与 forbidden 中的某个字符串匹配，我们就更新 start 为 end 的下一个位置。\n\n每次遍历到一个字符，我们都计算当前合法子字符串的长度，并与之前的最大长度进行比较，更新最大长度。\n\n最后，我们返回最大长度作为结果。\n\n下面是具体的实现代码：\n\ndef longestSubstring(word, forbidden):\n forbidden_set = set(forbidden)\n start = 0\n end = -1\n max_length = 0\n\n for i, char in enumerate(word):\n if char in forbidden_set:\n end = i\n max_length = max(max_length, end - start)\n\n start = end + 1\n\n return max(max_length, len(word) - start)\n\n这个算法的时间复杂度是 O(n)，其中 n 是字符串 word 的长度。因为我们需要遍历一次字符串 word，并在每次遍历时都进行一些常数时间的操作。