概览

1. 滑动窗口。

当遇到求最长或最短子串的问题时，可以考虑滑动窗口。滑动窗口是由两个控制窗口大小的指针left和right组成，一般一个指针滑动的目的是为了使窗口内的字符串满足要求，另一个指针滑动的目的是以贪心原则尽可能寻优，会一直移动到不满足条件为止。以求最大窗口为例，此时left移动是为了满足条件（因此left移动时处在不满足条件的状态下），right移动是为了求最优解（因此right移动时处在满足条件的状态下）。因此整体的思路如下：

  1. int left=0; // left为即将退出窗口的位置下标
  2. int right=0; // right为即将加入窗口的位置下标
  3. while(right<s.length()){
  4.     if(满足条件){
  5.         right++; 伴随的其他操作;
  6.     }
  7.     while(不满足条件){
  8.         left++; 伴随的其他操作;
  9.     }
  10. }

前文说到，两个指针中，有一个指针是用来满足要求，另一个是用来寻优。（以求最大窗口为例，left用来满足要求，right用来寻优）。对于用来满足要求的指针right，有以下 2 种移动方式：

  1. 当不满足要求时，多次移动left的正常方式。这种写法会出现left滑动多次致使窗口长度减小，因此需要用一个ans来记录历史最大窗口长度。有一种写法如下：

    1. int right = 0, ans = 0;
    2. for (int left = 0; i < n; ++i) {
    3. if (left != 0) {
    4.   // 左指针移动的伴随操作
    5. }
    6. while (right + 1 < s.length() && 满足right滑动条件 ) {
    7.   // 不断地移动右指针
    8.   right++;
    9.   // 右指针移动的伴随操作
    10. }
    11. // 更新ans
    12. ans = Math.max(ans, right - left + 1);
    13. }
    14. return ans;

  2. 当不满足要求时，通过滑动一次left后滑动一次right保证窗口长度不缩短，使窗口平移移动。

找到满足滑动right的条件，一般条件与窗口长度相关，当不满足滑动条件时，通过滑动一次left后滑动一次right保证窗口长度不缩短，从而屏蔽了那些虽然满足要求但长度已经比历史最长窗口长度小的结果。当然，滑动一次left后滑动一次right有可能仍然不满足要求，此时由于外层循环，窗口就会继续平移，直到满足要求，再开始移动right寻优。
代码方面，由于left在不满足要求时至多移动一次，因此内层“while(不满足要求)”改为“if(不满足要求)”，同时right++的位置进行了调整。模板如下：

  1. int left=0, right=0;
  2. while(right<s.length()){
  3.     更新right滑动条件中的相关量
  4.     // 不满足right滑动条件
  5.     if(不满足right滑动条件，与right-left+1有关){
  6.         left++;
  7.         更新right滑动条件中的相关量
  8.     }
  9.     right++;
  10. }
  11. // 窗口长度本应是right-left+1，但最后的right++多加了1
  12. return right-left;

2. 对字符串进行排序
  1. char[] array = str.toCharArray();
  2. Arrays.sort(array);
  3. String orderedStr = new String(array);

3. 忽略大小写比较字符
  1. Character.toLowerCase(s.charAt(i))==Character.toLowerCase(s.charAt(j))

3. 无重复字符的最长子串

思路：滑动窗口。
【写法1】按照模板b书写，用map记录窗口中的字母出现次数，right的移动条件是right-left+1-map.size()>0。

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         // 滑动窗口
  4.         int right=0;    // right为即将加入窗口的位置下标
  5.         int left=0;
  6.         Map<Character,Integer> map=new HashMap<Character,Integer>();
  7.         while(right<s.length()){
  8.             if(map.containsKey(s.charAt(right))){
  9.                 map.put(s.charAt(right),map.get(s.charAt(right))+1);
  10.             }else{
  11.                 map.put(s.charAt(right),1);
  12.             }
  13.             // 不满足right滑动条件：窗口长度大于map.size()，说明有重复
  14.             if(right-left+1-map.size()>0){
  15.                 if(map.get(s.charAt(left))==1){
  16.                     map.remove(s.charAt(left));
  17.                 }else{
  18.                     map.put(s.charAt(left),map.get(s.charAt(left))-1);
  19.                 }
  20.                 left++;
  21.             }
  22.             right++;
  23.         }
  24.         return right-left;
  25.     }
  26. }

【写法2】按照模板a书写。遍历左指针 i ，右指针只增不减（满足条件时增，条件为 !set.contains(s.charAt(right+1)) ）。这种写法会出现left滑动多次致使窗口长度减小，因此需要用一个ans来记录历史最大窗口长度。

  1. public int lengthOfLongestSubstring(String s) {
  2.     // 哈希集合，记录每个字符是否出现过
  3.     Set<Character> occ = new HashSet<Character>();
  4.     int n = s.length();
  5.     // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  6.     int rk = -1, ans = 0;    // rk为窗口中最靠右位置的下标
  7.     for (int i = 0; i < n; ++i) {
  8.         if (i != 0) {
  9.             // 左指针向右移动一格，移除一个字符
  10.             occ.remove(s.charAt(i - 1));
  11.         }
  12.         while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
  13.             // 不断地移动右指针
  14.             occ.add(s.charAt(rk + 1));
  15.             ++rk;
  16.         }
  17.         // 第 i 到 rk 个字符是一个极长的无重复字符子串
  18.         ans = Math.max(ans, rk - i + 1);
  19.     }
  20.     return ans;
  21. }

424. 替换后的最长重复字符

给定一个字符串 s 和一个整数 k ，找到最长的s的子串，满足改动不超过k个字符后，该子串全部为一样的字符，返回这个最长子串的长度。
思路：滑动窗口
本题中，窗口滑动的条件如下：窗口内除了重复次数最多的字母外，剩余字母个数<=k。实现方式：用int[26]记录每个字母在窗口中的出现次数。由于滑动right只会影响right处字母的出现次数，因此该窗口的相同字母最大出现次数只可能是max{right处字母的出现次数，曾经的窗口相同字母最大出现次数}。剩余字母个数=窗口长度-相同字母最大出现次数
由于只关心最长的窗口长度，因此让right++滑动，满足条件就更新最大长度，即便不满足条件，left只滑动一次，保证窗口长度不会缩短，因为即便left多滑几次得到了满足条件的窗口，其长度也肯定小于之前得到的窗口最大长度了。

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”。
思路：用两个map记录s和t，t的所有字符的出现次数。当smap中的每一项>=tmap，说明涵盖，满足要求。由于是求最小子串，right移动是为了满足要求，left移动是为了寻优。

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
思路：枚举所有子串，再进行回文判断。如果通过枚举起始与终止位置，需要O(n^2)，双指针检测回文需要O(n)，总复杂度为O(n^3)。然而，如果我们枚举中心位置，枚举只需O(n)，向外扩展与双指针检测回文需要O(n)，总复杂度降为了O(n^2)。