给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。
给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。
给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列 而不是子串。
(解决方案源:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/)
如果 s[j]s[j] 在 [i, j)[i,j) 范围内有与 j'j′ 重复的字符,我们不需要逐渐增加 ii 。 我们可以直接跳过 [i,j′] 范围内的所有元素,并将 i变为 j' + 1。
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>();
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;