Thursday, July 24, 2014

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

用左右两个指针,右指针往右移同时把char加进hashset里面,当hashset出现重复时,计算当前长度,移动左指针,一直到左指针指向重复的元素,把经过的元素移除hashset。重复以上过程。
public class Solution {
    //Time: O(n)  Space: O(n)
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        
        HashSet<Character> set = new HashSet<Character>();
        int left = 0;
        int i = 0;
        int max = 0;
        for (; i < s.length(); i++) {
            if (!set.contains(s.charAt(i))) {
                set.add(s.charAt(i));
            } else {
                max = Math.max(max, i - left);
                while (left < i && s.charAt(left) != s.charAt(i)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
        }
        max = Math.max(max, i - left);
        return max;
    }
}

No comments:

Post a Comment