3. Longest Substring Without Repeating Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[128];
        int start = 0;
        int end = 0;
        int maxLen = 0;
        while (end < s.length()) {
            char c = s.charAt(end);
            map[c]++;
            end++;
            while (map[c] > 1) {
                char prev = s.charAt(start);
                map[prev]--;
                start++;
            }
            maxLen = Math.max(maxLen, end - start);
        }
        return maxLen;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    /*
     abcabcbb
     01234567
     abc     
      bca
       cab
        abc 
    
    */
    public int lengthOfLongestSubstring(String s) {
        int lo = 0;
        int hi = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (hi < s.length()) {
            char c = s.charAt(hi);
            if (map.containsKey(Character.valueOf(c))) {
                lo = Math.max(map.get(Character.valueOf(c)), lo);
            }
            max = Math.max(max, hi - lo + 1);
            map.put(s.charAt(hi), hi + 1);
            hi++;
        }
        return max;
    }
    
    
    public int lengthOfLongestSubstring2(String s) {
        int lo = 0;
        int hi = 0;
        int max = 0;
        int[] freq = new int[256];
        while (hi < s.length()) {
            char c = s.charAt(hi);
            freq[c]++;
            while (freq[c] > 1) {
                char prev = s.charAt(lo);
                freq[prev]--;
                lo++;
            }
            max = Math.max(max, hi - lo + 1);
            hi++;
        }
        return max;
    }
}