Description

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

Solution:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<String, Integer> seq = new HashMap<String, Integer>();
        int cur = 0;
        int max = 0;
        for (int i = 0; i < s.length(); ++i) {
          if (seq.containsKey(String.valueOf(s.charAt(i)))) {
            Integer prevIndex = seq.get(String.valueOf(s.charAt(i)));
            if (i + 1 - prevIndex > cur) {
              cur = cur + 1;
            } else {
              cur = i + 1 - prevIndex;
            }
          } else {
            cur = cur + 1;
          }
          seq.put(String.valueOf(s.charAt(i)), i + 1);
          if (cur > max) {
            max = cur;
          }
        }
        return max;
    }
}

Attention

字符串从左向右遍历，遍历过程中将某个字符最近出现的index存进map中，因此map构建的是一个字符和index的对应关系。
在遍历过程中，首先判断当前的字符是否已经出现在map中，如果未出现，cur 加 1，其中cur是指当前位置向左的无重复的子字符串
长度。如果出现了，那么判断下，当前index和之前previndex之间的位置差值，是否 大于当前的cur，如果大于，说明，该字符不影响字符串生长，因而cur + 1
反之，说明影响了，将当前cur设置为两者的差值。每次判断之后，将当前字符put进map，实际上是重新更新位置的做法。

Submissions

Runtime: 23 ms, faster than 74.03% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 39.2 MB, less than 21.56% of Java online submissions for Longest Substring Without Repeating Characters.

Reference

public int lengthOfLongestSubstring(String s) {
    int i = 0, j = 0, max = 0;
    Set<Character> set = new HashSet<>();
    
    while (j < s.length()) {
        if (!set.contains(s.charAt(j))) {
            set.add(s.charAt(j++));
            max = Math.max(max, set.size());
        } else {
            set.remove(s.charAt(i++));
        }
    }
    
    return max;
}

Review

上面为高赞的回复，很精彩，尤其是 while循环里面的 remove i++，太精彩