76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
image.pngimage.png
image.png

  • 每次让R++一次,然后尽可能的移动L ```java class Solution { Map ori = new HashMap(); Map cnt = new HashMap();

    public String minWindow(String s, String t) {

    1.   int tLen = t.length();
    2.   for (int i = 0; i < tLen; i++) {
    3.       char c = t.charAt(i);
    4.       ori.put(c, ori.getOrDefault(c, 0) + 1);
    5.   }
    6.   int l = 0, r = -1;
    7.   int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
    8.   int sLen = s.length();
    9.   while (r < sLen) {
    10.       ++r;
    11.       if (r < sLen && ori.containsKey(s.charAt(r))) {
    12.           cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
    13.       }
    14.       while (check() && l <= r) {
    15.           if (r - l + 1 < len) {
    16.               len = r - l + 1;
    17.               ansL = l;
    18.               ansR = l + len;
    19.           }
    20.           if (ori.containsKey(s.charAt(l))) {
    21.               cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
    22.           }
    23.           ++l;
    24.       }
    25.   }
    26.   return ansL == -1 ? "" : s.substring(ansL, ansR);

    }

    public boolean check() {

    1.   Iterator iter = ori.entrySet().iterator(); 
    2.   while (iter.hasNext()) { 
    3.       Map.Entry entry = (Map.Entry) iter.next(); 
    4.       Character key = (Character) entry.getKey(); 
    5.       Integer val = (Integer) entry.getValue(); 
    6.       if (cnt.getOrDefault(key, 0) < val) {
    7.           return false;
    8.       }
    9.   } 
    10.   return true;

    } }

  3. <a name="lwLVd"></a>
  4. #### [32. 最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/)
  5. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/8429887/1612246959809-e6a632f5-8f42-46d2-bd25-88efcfea5219.png#align=left&display=inline&height=718&margin=%5Bobject%20Object%5D&name=image.png&originHeight=718&originWidth=720&size=52514&status=done&style=none&width=720)<br />动态规划可以做，也可以使用双指针
  7. - 对于任意‘（’、‘ ）’ 与他们匹配的都是唯一的一个
  8. - **括号序列合法 <=> 所有的前缀和>=0,并且总和=0**
  10. **做法：**
  12. - start表示当前一段的开头，cnt表示前缀和
  13. - （=1，）=-1
  14.    - cnt<0 =》 start = i+1,cnt=0 
  15.       - 为什么不是start++?因为对于当前的i（当前i指向的一定是‘）’）来说，在他之前没有一个左括号与他进行匹配，所以包含它的永远不是合法的。
  16.    - cnt>0 => 继续做
  17.    - cnt==0 ==》 [start,i]合法，可以更新最大值
  18. - 最后需要倒过来对称的做一次
  19. ```java
  20. class Solution {
  21.     public int longestValidParentheses(String s) {
  22.         int a = count(s);
  23.         // 对于(((( ))) 得到的是0,这时候需要反过来对称再做一次:
  24.         // 先倒过来,在左右括号相互转化
  25.         //((( ))))
  26.         char[] ch = s.toCharArray();
  27.         for (int i = 0, j = ch.length - 1; i < j; i++, j--) {
  28.             char c = ch[i];
  29.             ch[i] = ch[j];
  30.             ch[j] = c;
  31.         }
  32.         for (int i = 0; i < ch.length; i++) {
  33.             ch[i] = ch[i] == '(' ? ')' : '(';
  34.         }
  35.         return Math.max(a, count(new String(ch)));
  36.     }
  38.     int count(String s) {
  39.         int res = 0;
  40.         int start = 0;
  41.         int cnt = 0;
  42.         for (int i = 0; i < s.length(); i++) {
  43.             if (s.charAt(i) == '(') cnt++;
  44.             else {
  45.                 cnt--;
  46.                 if (cnt < 0) { // 当前所指向的右括号全局无法匹配,需要重新开始新的序列
  47.                     start = i + 1;
  48.                     cnt = 0;
  49.                 } else if (cnt == 0)
  50.                     res = Math.max(res, i - start + 1);
  51.             }
  52.         }
  53.         return res;
  54.     }
  55. }