查找不含重复字符的最长子串

1. 概述

在本教程中，我们将使用 Java 来比较几种查找不含重复字符的最长子串的方法。例如，在字符串 "CODINGISAWESOME" 中，不含重复字符的最长子串是 "NGISAWE"。

2. 暴力破解法

我们先从最直观的暴力解法入手。思路很简单粗暴：枚举所有子串，然后检查每个子串是否包含重复字符。

String getUniqueCharacterSubstringBruteForce(String input) {
    String output = "";
    for (int start = 0; start < input.length(); start++) {
        Set<Character> visited = new HashSet<>();
        int end = start;
        for (; end < input.length(); end++) {
            char currChar = input.charAt(end);
            if (visited.contains(currChar)) {
                break;
            } else {
                visited.add(currChar);
            }
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end);
        }
    }
    return output;
}

由于总共有 n(n+1)/2 个子串，所以该方法的时间复杂度为 ✅ **O(n²)**。

3. 优化解法：滑动窗口

接下来我们看一个更高效的解法。我们从左到右遍历字符串，并维护以下信息：

1. 当前不含重复字符的子串（通过 start 和 end 索引维护）
2. 已找到的最长子串 output
3. 一个记录字符最近出现位置的查找表 visited

String getUniqueCharacterSubstring(String input) {
    Map<Character, Integer> visited = new HashMap<>();
    String output = "";
    for (int start = 0, end = 0; end < input.length(); end++) {
        char currChar = input.charAt(end);
        if (visited.containsKey(currChar)) {
            start = Math.max(visited.get(currChar) + 1, start);
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end + 1);
        }
        visited.put(currChar, end);
    }
    return output;
}

每当我们遇到一个字符时，先检查它是否已经在当前窗口中出现过。如果出现过，则更新窗口的起始位置；否则继续扩展窗口。

因为我们只遍历一次字符串，✅ **时间复杂度为 O(n)**。

⚠️ 这种方法也被称为 **滑动窗口模式**，是处理子串问题的经典技巧。

4. 单元测试

最后，我们通过单元测试来验证实现是否正确：

@Test
void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected() {
    assertEquals("", getUniqueCharacterSubstring(""));
    assertEquals("A", getUniqueCharacterSubstring("A"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("AABCDEF"));
    assertEquals("ABCDEF", getUniqueCharacterSubstring("ABCDEFF"));
    assertEquals("NGISAWE", getUniqueCharacterSubstring("CODINGISAWESOME"));
    assertEquals("be coding", getUniqueCharacterSubstring("always be coding"));
}

测试覆盖了边界情况和典型用例，确保算法在各种场景下都能正确运行。

5. 小结

在这篇文章中，我们学习了如何使用滑动窗口技巧来高效地查找不含重复字符的最长子串。

一如既往，源码可以在 GitHub 上找到。