3. Longest Substring Without Repeating Characters

题目描述：

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题目翻译

给定一个字符串，找到不含重复字符的最长子串。

例子：

给定"abcabcbb"的答案是"abc"，长度是3。

给定"bbbbb"的答案是"b"，长度为1。

给定"pwwkew"的答案是"wke"，长度为3。请注意，答案必须是子字符串，"pwke"是子序列，而不是子字符串。

解题方案

标签： String

思路：

• 遍历字符串，使用 head 来标记当前子串的右侧头位置，tail 来标记当前子串的左侧尾位置，sub[tail,head]表示当前子串
• 当sub[tail,head]中所有字符都不重复时，则head++
• 当sub[tail,head]中包含重复字符时，则tail++，直到所有字符都不重复为止
• 根据当前不重复子串，更新最大长度res

代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> hset = new HashSet();
        int res = 0;
        int tail = 0;
        for(int head=0;head<s.length();head++){
            while(tail<=head && hset.contains(s.charAt(head))){
                hset.remove(s.charAt(tail));
                tail++;
            }
            hset.add(s.charAt(head));
            res = Math.max(res,head-tail+1);
        }
        return res;
    }
}