#P4007. 无重复字符的最长字串
-
ID: 2214
Tried: 402
Accepted: 93
Difficulty: 3
无重复字符的最长字串
题目内容
给定一个字符串s，请你找出其中不含有重复字符的 最长子串 的长度
输入描述
一行字符串s
输出描述
一个整数，表示答案。
样例1
输入
abcabcbb
输出
3
说明
因为无重复字符的最长子串是 "abc"，所以其长度为 3。
样例2
输入
bbbbb
输出
1
说明
因为无重复字符的最长子串是 "b"，所以其长度为1。
样例3
输入
pwwkew
输出
3
说明
因为无重复字符的最长子串是 "wke"，所以其长度为3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示
- 0<=s.length<=5∗104
- s 由
英文字母、数字、符号和空格组成
无重复字符的最长字串
题解思路
本题要求找到字符串中最长的无重复字符子串的长度，可以使用 滑动窗口（Sliding Window） + 哈希集合（HashSet） 进行优化。
-
定义双指针（左右指针）
left指向当前窗口的起点。right指向当前窗口的终点，不断向右扩展。
-
使用哈希集合存储当前窗口内的字符
- 当
right指向的字符未在窗口中出现时，加入集合，并更新最大长度max_length。 - 当
right指向的字符已在窗口中出现时，移动left指针，直到right指向的字符不再重复。
- 当
-
重复上述步骤，直到
right遍历完整个字符串。
复杂度分析
- 时间复杂度：O(n)，
right指针遍历n个字符，每个字符最多被left指针访问一次。 - 空间复杂度：O(min(n, |Σ|))，
Σ是字符集大小，使用集合存储窗口中的字符。
代码
注意题目输入里有空格
Python 代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希集合存储窗口内的字符
char_set = set()
left = 0 # 窗口左指针
max_length = 0 # 记录最长子串的长度
for right in range(len(s)): # 右指针遍历字符串
while s[right] in char_set: # 如果字符重复
char_set.remove(s[left]) # 移除左指针对应的字符
left += 1 # 左指针右移
char_set.add(s[right]) # 将新字符加入集合
max_length = max(max_length, right - left + 1) # 更新最大长度
return max_length
# 示例测试
if __name__ == "__main__":
s = input()
solution = Solution()
print(solution.lengthOfLongestSubstring(s))
Java 代码
import java.util.HashSet;
import java.util.Scanner;
public class Main {
public class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> charSet = new HashSet<>(); // 哈希集合存储窗口内的字符
int left = 0; // 窗口左指针
int maxLength = 0; // 记录最长子串的长度
for (int right = 0; right < s.length(); right++) { // 右指针遍历字符串
while (charSet.contains(s.charAt(right))) { // 如果字符重复
charSet.remove(s.charAt(left)); // 移除左指针对应的字符
left++; // 左指针右移
}
charSet.add(s.charAt(right)); // 将新字符加入集合
maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
}
return maxLength;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
Main main = new Main();
Solution solution = main.new Solution();
System.out.println(solution.lengthOfLongestSubstring(s));
scanner.close();
}
}
C++ 代码
#include <iostream>
#include <unordered_set>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> charSet; // 哈希集合存储窗口内的字符
int left = 0; // 窗口左指针
int maxLength = 0; // 记录最长子串的长度
for (int right = 0; right < s.length(); right++) { // 右指针遍历字符串
while (charSet.find(s[right]) != charSet.end()) { // 如果字符重复
charSet.erase(s[left]); // 移除左指针对应的字符
left++; // 左指针右移
}
charSet.insert(s[right]); // 将新字符加入集合
maxLength = max(maxLength, right - left + 1); // 更新最大长度
}
return maxLength;
}
};
int main() {
string s;
getline(cin, s); // 读取输入
Solution solution;
cout << solution.lengthOfLongestSubstring(s) << endl;
return 0;
}