题目

给定一个字符串，给出其中无重复字符的最长子串长度

解题

记录每个字符的下标最大值，再往后遍历的过程中判断是否已有该字符记录，如果有表示有重复，则在i到j中间为可能最长子串。如果排除子串的问题呢？通过双指针，一个快，一个慢，快指针循环往后遍历，慢指针根据是否与慢指针相同字符的位置做位移。因此可以排除掉子串的问题

比如i=5,j=10的位置都是a，但其中有i1=7，j2=8的位置都是b，那么5~10必然不能取。那么在快指针向后移动经过8位置时，判断7位置是重复字符，则将慢指针更新到8位置，就不会有上面的那种情况。

//利用动态规划的思想
public int findMaxSubStringWithoutDuplicateChar(String source){
  int start = 0;
  int end = 0;
  int res = 0;
  Map<Character, Integer> charMaxIndexMap = new HashMap<>();
  while (end < source.length()) {
    char endChar = source.charAt(end);
    if (charMaxIndexMap.containsKey(endChar)) {
      start = Math.max(start, charMaxIndexMap.get(endChar) + 1);
      res = Math.max(res, end - start + 1);
    } else {
      res = Math.max(res, end - start + 1);
    }
    charMaxIndexMap.put(endChar, end);
    end++;
  }
  return res;
}

//滑动窗口
public static int getLongestSubStringWithWindow(String source) {
  if(source==null||source.length()==0){
    return 0;
  }
  Set<Character> window = new HashSet<>();
  int slow = 0;
  int fast = 1;
  int result = 1;
  int length = source.length();
  window.add(source.charAt(slow));
  while (fast < length) {
    if (window.add(source.charAt(fast))) {
      fast++;
    } else {
      while (source.charAt(slow) != source.charAt(fast)) {
        window.remove(source.charAt(slow));
        slow++;
      }
      window.remove(source.charAt(slow));
      slow++;
    }
    result = Math.max(result, fast - slow);
  }
  return result;
}

//地图记录模式，逐步更新已走过的字符，然后用于当前最右字符
public static int getLongestSubStringOfWalked(String source) {
  int length = source.length();
  int left = 0;
  int right = 0;
  int result = 0;
  boolean[] walkedRecord = new boolean[256];
  while (right < length) {
    int curChar = (int)source.charAt(right);
    while (left < right && walkedRecord[curChar]) {
      walkedRecord[(int)source.charAt(left++)] = false;
    }
    walkedRecord[curChar] = true;
    result = Math.max(result, right - left + 1);
    right++;
  }
  return result;
}