最长合法子字符串的长度

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.

/*
 * 思路：
 * 1. 使用双指针（滑动窗口）方法来寻找最长的合法子字符串。
 * 2. 使用 Java Stream 处理字符串。
 * 3. 使用一个哈希集来存储所有 forbidden 子字符串。
 * 4. 当窗口内的子字符串包含 forbidden 中的任何字符串时，移动 start 指针以缩小窗口。
 * 5. 记录合法子字符串的最大长度。
 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int longestValidSubstring(String word, String[] forbidden) {
        Set<String> forbiddenSet = new HashSet<>(Arrays.asList(forbidden));

        int maxLength = 0;
        int start = 0;
        for (int end = 0; end < word.length(); end++) {
            for (int len = 1; len <= 10 && end - len + 1 >= start; len++) {
                if (forbiddenSet.contains(word.substring(end - len + 1, end + 1))) {
                    start = end - len + 2;
                    break;
                }
            }
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}

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

O(n * maxLen)

O(f + l)