---
tags: Leetcode
---
# Longest Substring Without Repeating Characters

## By using HashSet

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j)); // set.add(s.charAt(j++)) =  set.add(s.charAt(j)); j++;
                j++;
                
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i));// 這裡有點特別，為什麼一開始一定是 remove 0 ( i == 0 )?
                i++;
                
            }
        }
        return ans;
    }
}

## By using HashMap

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        // try to extend the range [i, j]
        for( int j = 0, i = 0; j < n; j++ ){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(map.get(s.charAt(j)), i ); // 若map.get()得到的值小於i值，則會計算錯誤 ex"abba" 會算到第一個 a = 1 而不是 2 
            }
            
            ans = Math.max( ans, j - i + 1);
            map.put(s.charAt(j), j+1);
        }
        return ans;
    }
}

## Replacing the Map with an Integer Array
If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

## Note

A & B are same

A
set.add(s.charAt(j++));

B
set.add(s.charAt(j)); 
j++;