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.

Solution

Pay attention when moving the 'start' pointer forward.

Complexity

时间复杂度 O(n)，空间复杂度 O(n)

Code

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() < 1) return 0;
        int len = s.length();
        int maxCount = 0;
        int curStart = -1;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < len ;i++){
            if (map.containsKey(s.charAt(i))){
                curStart = Math.max(curStart,map.get(s.charAt(i)));
            }
            map.put(s.charAt(i),i);
            maxCount = Math.max(maxCount, i-curStart);
        }
        
        return maxCount;
    }
}

Reference

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] hash = new boolean[256];
        Arrays.fill(hash,false);
        int n = s.length();
        if (n <= 1) return n;
        int start = 0, end = 0, res = 0;
        while (end < n && start + res < n) {
            if (hash[s.charAt(end)] == false) {
                hash[s.charAt(end++)] = true;
            } else {
                hash[s.charAt(start++)] = false;
            }
            res = Math.max(res, end - start);
        }
        return res;
    }
}