Longest Substring Without Repeating Characters

leetcode 3

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.

Solution. An awesome solution is from here. It has two pointers, left and right. s[left, right] has no duplicate.

Iterate right, if s[right] is not in HashSet, then put it in, and update ans = max(ans, right – left).

If s[right] is already in HashSet, we need to loop from left and remove s[left], until there is no s[right] in HashSet.

If the string is [a b c d e f g h i e j k l], then the process is like:

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, right = 0, ans = 0;
    while (right < s.length()) {
        if (set.contains(s.charAt(right))) {    // has duplicate, move left until there is no duplicate between [left, right]
            set.remove(s.charAt(left++));
        }
        else {
            set.add(s.charAt(right++)); // has no duplicate between [left, right], move right
            ans = Math.max(ans, right - left);
        }
    }
    return ans;
}

Check my code on github.