一、面试问题
给定一个由小写字母组成的字符串s，找出其中无重复字符的最长子串的长度。
示例 1：
输入：s = "abcdefabcbb"
输出：6
解释：无重复字符的最长子串是 "abcdef"。
示例 2：
输入：s = "aaa"
输出：1
解释：无重复字符的最长子串是 "a"。
二、【朴素解法】遍历每个索引开始的子串 —— 时间 O (n²)，空间 O (1)
(一) 解法思路
从每一个索引位置开始，查找以该位置为起点的无重复字符的最长子串长度。所有这些长度中的最大值，就是最终答案。
为了找到从某个索引开始的最长无重复子串，我们创建一个大小为 26 的 visited 数组，用来记录子串中已经出现过的字符。vis[0]对应字符 'a'，vis[1]对应字符 'b'，vis[2]对应字符 'c'，依此类推。
(二) 使用 5 种语言实现
1. C++
#include <iostream> #include <vector> using namespace std; // 函数：查找无重复字符的最长子串长度（暴力枚举法） int longestUniqueSubstr(string &s) { int n = s.size(); // 字符串长度 int res = 0; // 存储最终结果（最大长度） // 外层循环：遍历每一个起始位置 i for (int i = 0; i < n; i++) { // 新建一个长度为 26 的数组，标记小写字母是否出现过 // 每次更换起点，都重置 visited 数组 vector<bool> vis(26, false); // 内层循环：从 i 开始向后扩展子串 for (int j = i; j < n; j++) { // 如果当前字符已经出现过 → 停止扩展 if (vis[s[j] - 'a'] == true) break; // 否则：更新最大长度，并标记字符已访问 else { res = max(res, j - i + 1); // 计算当前子串长度，更新最大值 vis[s[j] - 'a'] = true; // 标记该字符已出现 } } } return res; } // 主函数测试 int main() { string s = "geeksforgeeks"; cout << longestUniqueSubstr(s); // 输出：7 return 0; }2. Java
class DSA { // 暴力解法：查找无重复字符的最长子串长度 static int longestUniqueSubstr(String s){ int n = s.length(); // 字符串长度 int res = 0; // 记录最大长度 // 遍历每一个起点 i for (int i = 0; i < n; i++) { // 新建数组：标记 26 个小写字母是否被访问过 boolean[] vis = new boolean[26]; // 从起点 i 开始，向后扩展终点 j for (int j = i; j < n; j++) { // 如果当前字符已经出现过 → 停止扩展 if (vis[s.charAt(j) - 'a'] == true) break; // 没有重复：更新最大长度，标记字符已访问 else { res = Math.max(res, j - i + 1); vis[s.charAt(j) - 'a'] = true; } } } return res; } // 测试主函数 public static void main(String[] args){ String s = "geeksforgeeks"; System.out.println(longestUniqueSubstr(s)); // 输出 7 } }3. Python
# 暴力解法：无重复字符的最长子串长度 # 思路：枚举所有起点，逐个扩展终点，用数组记录字符是否出现 def longestUniqueSubstr(s): n = len(s) # 字符串长度 res = 0 # 保存最长长度 # 遍历每一个起点 i for i in range(n): # 初始化 26 个小写字母为未访问 vis = [False] * 26 # 从 i 开始，向后扩展子串终点 j for j in range(i, n): # 计算当前字符对应的索引（a=0, b=1...z=25） idx = ord(s[j]) - ord('a') # 如果当前字符已经出现过，直接停止扩展 if vis[idx]: break # 没有重复，更新最大长度，并标记字符已访问 res = max(res, j - i + 1) vis[idx] = True return res if __name__ == "__main__": s = "geeksforgeeks" print(longestUniqueSubstr(s)) # 输出 74. C#
using System; class GfG { // 暴力解法：求无重复字符的最长子串长度 static int longestUniqueSubstr(string s) { int n = s.Length; // 字符串长度 int res = 0; // 记录最大长度 // 遍历每一个起点 i for (int i = 0; i < n; i++) { // 初始化 26 个小写字母的访问标记数组 bool[] vis = new bool[26]; // 从起点 i 开始扩展终点 j for (int j = i; j < n; j++) { // 当前字符已经出现过 → 停止扩展 if (vis[s[j] - 'a'] == true) break; // 无重复：更新最大长度，并标记已访问 else { res = Math.Max(res, j - i + 1); vis[s[j] - 'a'] = true; } } } return res; } // 主函数测试 static void Main() { string s = "geeksforgeeks"; Console.WriteLine(longestUniqueSubstr(s)); // 输出 7 } }5. JavaScript
function longestUniqueSubstr(s) { let n = s.length; // 字符串长度 let res = 0; // 记录最长无重复子串的长度 // 遍历每一个起始位置 i for (let i = 0; i < n; i++) { // 初始化 26 个小写字母的访问标记数组（全部未访问） let vis = new Array(26).fill(false); // 从 i 开始，向后扩展子串的结束位置 j for (let j = i; j < n; j++) { // 计算当前字符对应的索引 (a=0, b=1 ... z=25) let idx = s.charCodeAt(j) - 'a'.charCodeAt(0); // 如果当前字符已经出现过，直接停止扩展 if (vis[idx] === true) break; // 没有重复，更新最大长度，并标记字符已访问 else { res = Math.max(res, j - i + 1); vis[idx] = true; } } } return res; } // 测试代码 let s = "geeksforgeeks"; console.log(longestUniqueSubstr(s)); // 输出: 7(三)代码输出和算法复杂度
输出：
7时间复杂度：O(n²)
空间复杂度：O(k)
三、【最优解法-1】滑动窗口 —— 时间复杂度 O (n)，空间复杂度 O (1)
(一) 解法思路
核心思路是维护一个无重复字符的窗口。窗口初始化为单个字符。我们不断在窗口右侧进行扩展，直到出现重复字符。当遇到重复字符时，从窗口左侧移除字符。我们全程记录窗口的最大长度。
详细步骤如下：
- 初始化两个指针
left和right均为 0，用于界定当前考察的窗口。 right指针从左向右移动，不断扩展当前窗口。- 若
right指针指向的字符未被访问过，则将其标记为已访问。 - 若
right指针指向的字符已被访问过，说明出现了重复字符。此时将left指针向右移动，并将经过的字符标记为未访问，直到重复字符不再属于当前窗口。 - 计算当前窗口长度（
right - left + 1），并相应更新答案。
(二) 使用 5 种语言实现
1. C++
#include <iostream> #include <vector> using namespace std; // 滑动窗口解法：无重复字符的最长子串 int longestUniqueSubstr(string& s) { // 边界：空串或单个字符直接返回长度 if (s.length() == 0 || s.length() == 1) return s.length(); int res = 0; // 记录最大长度 vector<bool> vis(26, false); // 标记字符是否在窗口中 // 滑动窗口的左右指针 int left = 0, right = 0; while (right < s.length()) { // 如果当前字符已经在窗口中（重复） // 不断移动左指针，并把移出窗口的字符标记为未访问 while (vis[s[right] - 'a'] == true) { vis[s[left] - 'a'] = false; left++; } // 把当前字符加入窗口，标记为已访问 vis[s[right] - 'a'] = true; // 更新最长子串长度 res = max(res, (right - left + 1)); // 右指针扩展窗口 right++; } return res; } int main() { string s = "geeksforgeeks"; cout << longestUniqueSubstr(s); // 输出 7 return 0; }2. Java
class DSA { // 滑动窗口解法：无重复字符的最长子串长度 static int longestUniqueSubstr(String s) { // 边界处理：空串或单个字符直接返回长度 if (s.length() == 0 || s.length() == 1) return s.length(); int res = 0; // 保存最大长度 boolean[] vis = new boolean[26]; // 标记字符是否在窗口中 // 滑动窗口的左右指针 int left = 0, right = 0; while (right < s.length()) { // 如果当前字符已在窗口中（重复） // 不断移动左指针，将移出窗口的字符标记为未访问 while (vis[s.charAt(right) - 'a'] == true) { vis[s.charAt(left) - 'a'] = false; left++; } // 将当前字符加入窗口，标记为已访问 vis[s.charAt(right) - 'a'] = true; // 更新最长无重复子串长度 res = Math.max(res, (right - left + 1)); // 右指针右移，扩展窗口 right++; } return res; } // 测试主函数 public static void main(String[] args) { String s = "geeksforgeeks"; System.out.println(longestUniqueSubstr(s)); // 输出 7 } }3. Python
# 定义小写字母总数量 26 MAX_CHAR = 26 def longestUniqueSubstr(s): # 边界处理：空字符串或单个字符，直接返回长度 if len(s) == 0 or len(s) == 1: return len(s) res = 0 # 记录最长无重复子串的长度 vis = [False] * 26 # 标记字符是否在当前窗口中 # 滑动窗口的左右指针，初始都指向开头 left = 0 right = 0 while right < len(s): # 如果当前字符已经在窗口内（重复） # 不断移动左指针，并将移出窗口的字符标记为未访问 while vis[ord(s[right]) - ord('a')] == True: vis[ord(s[left]) - ord('a')] = False left += 1 # 将当前字符加入窗口，标记为已访问 vis[ord(s[right]) - ord('a')] = True # 更新最大长度：当前窗口长度 = right - left + 1 res = max(res, (right - left + 1)) # 右指针右移，扩大窗口 right += 1 return res # 测试代码 if __name__ == "__main__": s = "geeksforgeeks" print(longestUniqueSubstr(s)) # 输出 74. C#
using System; class DSA { // 滑动窗口解法：无重复字符的最长子串长度 static int longestUniqueSubstr(string s) { // 边界处理：空串或单个字符直接返回长度 if (s.Length == 0 || s.Length == 1) return s.Length; int res = 0; // 记录最大长度 bool[] vis = new bool[26]; // 标记字符是否在窗口中 // 滑动窗口左右指针 int left = 0, right = 0; while (right < s.Length) { // 如果当前字符已存在于窗口中（重复） // 移动左指针，并将移出窗口的字符标记为未访问 while (vis[s[right] - 'a'] == true) { vis[s[left] - 'a'] = false; left++; } // 将当前字符加入窗口，标记为已访问 vis[s[right] - 'a'] = true; // 更新最长子串长度 res = Math.Max(res, (right - left + 1)); // 右指针右移，扩大窗口 right++; } return res; } // 测试主函数 static void Main() { string s = "geeksforgeeks"; Console.WriteLine(longestUniqueSubstr(s)); // 输出 7 } }5. JavaScript
function longestUniqueSubstr(s) { // 边界处理：空串或单个字符直接返回长度 if (s.length === 0 || s.length === 1) return s.length; let res = 0; // 记录最长无重复子串长度 let vis = new Array(26).fill(false); // 标记字符是否在窗口中 // 滑动窗口的左右指针 let left = 0, right = 0; while (right < s.length) { // 获取当前字符的索引（a=0, b=1...） let currIdx = s[right].charCodeAt(0) - 'a'.charCodeAt(0); // 如果当前字符重复，移动左指针并清除标记 while (vis[currIdx] === true) { let leftIdx = s[left].charCodeAt(0) - 'a'.charCodeAt(0); vis[leftIdx] = false; left++; } // 标记当前字符已访问 vis[currIdx] = true; // 更新最大长度 res = Math.max(res, right - left + 1); // 右指针扩大窗口 right++; } return res; } // 测试代码 const s = "geeksforgeeks"; console.log(longestUniqueSubstr(s)); // 输出 7(三)代码输出和算法复杂度
输出：
7时间复杂度：O(n)
空间复杂度：O(k)
四、【最优解法-2】记录字符最后出现位置 —— 时间复杂度 O (n)，空间复杂度 O (1)
(一) 解法思路
该方法会记录已访问字符最后一次出现的下标。核心思路是维护一个无重复字符的窗口。从第一个字符开始，不断在右侧扩展窗口，直到遇到重复字符。
当遇到重复字符时，检查该重复字符的最后出现下标：
- 如果重复字符的最后下标 ≥ 当前窗口的起始下标，则将当前窗口的起始下标更新为重复字符最后下标 + 1，以此排除重复字符。
- 如果重复字符的最后下标 < 当前窗口的起始下标，说明该重复字符已经不在当前窗口内，窗口大小保持不变。
遍历完所有字符后，最大的窗口长度即为答案。
(二) 使用 5 种语言实现
1. C++
#include <iostream> #include <vector> using namespace std; // 最优解法：记录每个字符最后出现的位置，滑动窗口直接跳跃 int longestUniqueSubstr(string &s) { int n = s.size(); int res = 0; // 保存最终答案：最长无重复子串长度 // 记录26个小写字母最后一次出现的下标，初始化为 -1 vector<int> lastIndex(26, -1); // 当前窗口的起始位置（左指针） int start = 0; // end 是窗口的右指针，不断向右扩展 for (int end = 0; end < n; end++) { // 如果当前字符出现过，直接把窗口起点跳到 重复位置+1 // 这一句整合了判断逻辑，非常简洁 start = max(start, lastIndex[s[end] - 'a'] + 1); // 更新最长窗口长度 res = max(res, end - start + 1); // 更新当前字符最后一次出现的位置 lastIndex[s[end] - 'a'] = end; } return res; } int main() { string s = "geeksforgeeks"; cout << longestUniqueSubstr(s); // 输出 7 return 0; }2. Java
class DSA { // 最优解法：记录字符最后出现位置 + 滑动窗口跳跃 static int longestUniqueSubstr(String s) { int n = s.length(); int res = 0; // 记录26个小写字母最后出现的下标，全部初始化为 -1 int[] lastIndex = new int[26]; for (int i = 0; i < 26; i++) { lastIndex[i] = -1; } // 滑动窗口的起始位置（左指针） int start = 0; // end 是窗口右指针，向右扩展窗口 for (int end = 0; end < n; end++) { // 获取当前字符的索引 int idx = s.charAt(end) - 'a'; // 更新窗口左边界： // 如果当前字符在窗口内重复，左边界直接跳到【上次出现位置 + 1】 start = Math.max(start, lastIndex[idx] + 1); // 更新最长无重复子串长度 res = Math.max(res, end - start + 1); // 更新当前字符最后出现的位置 lastIndex[idx] = end; } return res; } // 测试主函数 public static void main(String[] args) { String s = "geeksforgeeks"; System.out.println(longestUniqueSubstr(s)); // 输出 7 } }3. Python
def longestUniqueSubstr(s): n = len(s) res = 0 # 存储最长无重复子串的长度 # 记录26个小写字母最后一次出现的下标，初始化为 -1 lastIndex = [-1] * 26 # 滑动窗口的起始位置（左指针） start = 0 # end 是窗口右指针，向右遍历扩展窗口 for end in range(n): # 计算当前字符对应的索引（a=0, b=1...） idx = ord(s[end]) - ord('a') # 更新窗口左边界： # 如果当前字符在窗口内重复，左边界直接跳到【上次出现位置 + 1】 start = max(start, lastIndex[idx] + 1) # 更新最大窗口长度 res = max(res, end - start + 1) # 更新当前字符最后一次出现的位置 lastIndex[idx] = end return res if __name__ == "__main__": s = "geeksforgeeks" print(longestUniqueSubstr(s)) # 输出 74. C#
using System; class DSA { // 定义最大字符数（小写字母 26 个） const int MAX_CHAR = 26; // 最优解法：记录字符最后出现位置 + 滑动窗口（直接跳跃） public static int longestUniqueSubstr(string s) { int n = s.Length; int res = 0; // 保存最长无重复子串长度 // 记录每个字符最后出现的下标，全部初始化为 -1 int[] lastIndex = new int[MAX_CHAR]; for (int i = 0; i < MAX_CHAR; i++) { lastIndex[i] = -1; } // 滑动窗口的左边界（起点） int start = 0; // 右边界 end 不断向右扩展窗口 for (int end = 0; end < n; end++) { // 如果当前字符重复，直接把左边界跳到重复位置的下一位 start = Math.Max(start, lastIndex[s[end] - 'a'] + 1); // 更新最大窗口长度 res = Math.Max(res, end - start + 1); // 更新当前字符最后出现的位置 lastIndex[s[end] - 'a'] = end; } return res; } // 测试主函数 static void Main() { string s = "geeksforgeeks"; Console.WriteLine(longestUniqueSubstr(s)); // 输出 7 } }5. JavaScript
function longestUniqueSubstr(s) { const n = s.length; let res = 0; // 存储最长无重复子串的长度 // 记录26个小写字母最后一次出现的下标，全部初始化为 -1 const lastIndex = new Array(26).fill(-1); // 滑动窗口的起始位置（左指针） let start = 0; // end 作为右指针，向右遍历扩展窗口 for (let end = 0; end < n; end++) { // 获取当前字符对应的索引（a=0, b=1...） const idx = s.charCodeAt(end) - 'a'.charCodeAt(0); // 更新窗口左边界： // 如果当前字符在窗口内重复，左边界直接跳到【上次出现位置 + 1】 start = Math.max(start, lastIndex[idx] + 1); // 更新最大窗口长度 res = Math.max(res, end - start + 1); // 更新当前字符最后一次出现的位置 lastIndex[idx] = end; } return res; } // 测试代码 const s = "geeksforgeeks"; console.log(longestUniqueSubstr(s)); // 输出: 7(三)代码输出和算法复杂度
输出：
7时间复杂度：O(n)
空间复杂度：O(k)
