Description:

Given a string, find the length of the longest substring without repeating characters.

Examples:

1. Given "abcabcbb", the answer is "abc", which the length is 3.
2. Given "bbbbb", the answer is "b", with the length of 1.
3. 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.

思路：

利用HashMap，把字符當(dāng)做key，把字符最后出現(xiàn)的index當(dāng)做value存在map中，儲存的過程其實就是在對字符串的遍歷，當(dāng)發(fā)現(xiàn)重復(fù)的字符時，更新結(jié)果。

Solution

public int longest_substring_without_repeating(String s){
  int result = 0;
  HashMap<Character, Integer> map = new HashMap<>(); //store the current index of the character
  for(int i = 0, j = 0; j < s.length(); j++){
    char cur_char = s.charAt(j);
    if(map.containsKey(cur_char)){
      i = Math.max(i, map.get(cur_char)+1);
    }
    map.put(cur_char, j);
    result = Math.max(result, j - i + 1);
  }
  return result;
}