题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
假设字符串中只包含从 a 到 z 的字符。
数据范围
输入字符串长度 [0,1000] 。
样例
输入:"abcabc"
输出:3
Java 代码
class Solution {
public int longestSubstringWithoutDuplication(String s) {
// 统计每个字符最后一次出现的位置
Map<Character, Integer> map = new HashMap<>();
int result = 0;
// 记录当前不重复子字符串的长度
int curLen = 0;
int left = 0, right = 0;
while(right < s.length()){
char c = s.charAt(right);
// 如果当前字符还未出现在map中,则更新map并将curLen加1
if(!map.containsKey(c)){
curLen++;
// 如果当前字符出现在map中,需要移动左指针到当前字符最后一次出现的位置
}else{
// 左指针需要移动到当前位置字符最后一次出现的位置(因为当前位置还未进行更新,准确来说是倒数第二次出现的位置)
// 之所以不直接令left=map.get(c),因为可能上次left指针已经移到当前要更新的位置后
left = Math.max(left, map.get(c));
curLen = right - left;
}
// 每次都需要更新当前位置字符在map中的映射
map.put(c, right);
result = Math.max(result, curLen);
// 每次都要移动右指针
right++;
}
return result;
}
}