给定一个字符串和最多10个禁用词，需找出不包含任一禁用词作为子串的最长连续子串长度；本文介绍基于双指针与后缀匹配优化的 o(mn) 解法，避免暴力截取与 contains 导致的 o(mn²) 开销。
给定一个字符串和最多10个禁用词，需找出不包含任一禁用词作为子串的最长连续子串长度；本文介绍基于双指针与后缀匹配优化的 o(mn) 解法，避免暴力截取与 contains 导致的 o(mn²) 开销。
在字符串处理类问题中，“最长合法子串”常可通过滑动窗口（双指针）解决，但关键在于如何高效判断窗口内是否新增了非法模式。原代码使用 substring() + contains() 的组合，每次迭代都重建子串并遍历所有禁用词进行子串搜索，导致最坏时间复杂度高达 O(m·n²)（其中 n 为字符串长度，m 为禁用词数量），无法应对 10⁵ 规模输入。
核心优化思路是：不检查整个子串是否含禁用词，而只检查以右端点 i 结尾的新后缀是否恰好匹配某个禁用词。因为当左指针 j 固定时，仅当新加入字符 s[i] 使 s[j..i] 首次出现禁用词时，该禁用词必然以位置 i 结尾。因此，我们只需验证所有禁用词是否为 s[?..i] 的后缀——即检查 s[i−len+1..i] 是否等于某禁用词。
由此可设计 O(mn) 算法：
- 维护滑动窗口 [j, i]（左闭右闭，长度为 i−j+1）；
- 对每个 i，从 j 开始向右收缩（j++），直到 s[j..i] 不以任何禁用词结尾；
- 每次收缩仅需检查至多 m 个禁用词，且每个禁用词比较最多 10 次（因词长 ≤10），故单次 endsWith 为 O(m)；
- 关键性质：i 和 j 各自最多递增 n 次，总操作数 ≤ 2n，因此整体时间复杂度为 O(mn)，空间复杂度 O(1)。
以下是完整、可运行的 Java 实现：
public int solve(String s, List<string> words) {
if (s == null || s.isEmpty()) return 0;
int n = s.length(), j = 0, ans = 0;
for (int i = 0; i words) {
for (String word : words) {
if (endsWith(s, begin, end, word)) {
return true;
}
}
return false;
}
// 判断 s[begin..end] 是否以 word 结尾
private boolean endsWith(String s, int begin, int end, String word) {
int len = word.length();
int startIdx = end - len + 1; // word 在 s 中应起始的位置
if (startIdx <p>⚠️ 注意事项：</p>
<ul>
<li>禁用词长度上限为 10，因此 endsWith 内部循环为常数级，这是 O(mn) 成立的前提；</li>
<li>原题示例 s = "helloworld", words = ["wor", "rld"]：当 i=6（对应 'o'，索引从0开始），s[0..6]="hellowo"，检查后缀 "owo"、"lowo" 等均不匹配；而 i=7 时 s[0..7]="hellowor"，后缀 "wor" 匹配，触发 j++，最终最大合法长度为 7；</li>
<li>若需返回具体子串而非长度，可在更新 ans 时同步记录 bestJ 和 bestI；</li>
<li>本解法未使用 Trie 或 KMP，因其在 m ≤ 10 且 word.length ≤ 10 场景下无必要开销；若 m 显著增大（如 ≥1000），则建议构建 Aho-Corasick 自动机实现 O(n)。</li>
</ul>
<p>总结：通过将“全局子串检测”降维为“右对齐后缀匹配”，结合双指针的单调性保证，我们成功将时间复杂度从不可接受的 O(mn²) 优化至线性级别 O(mn)，兼顾简洁性与工程实用性。</p></string>
