leetcode 76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

class Solution {
    public String minWindow(String s, String t) {

        int left,right,count,minLen= Integer.MAX_VALUE;
        int start=0,end=0;

        //needs存储t的<字符,出现次数>,windows存储<s中与t中字符相同的字符,出现次数>
        HashMap<Character,Integer> needs = new HashMap<>();
        HashMap<Character,Integer> windows = new HashMap<>();

        //初始化needs
        for(int i=0;i<t.length();i++){
            //needs.getOrDefault(t.charAt(i),0)+1 含义是：needs如果包含t.charAt(i)，
            //则取出值+1;不包含取0+1
            needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0)+1);
        }

        left=right=count=0;
        while(right <s.length()){
            //获取字符
            char temp=s.charAt(right);
            //如果是t中字符，在windows里添加，累计出现次数
            if(needs.containsKey(temp)){
                windows.put(temp,windows.getOrDefault(temp,0)+1);
                //注意：Integer不能用==比较，要用compareTo
                if(windows.get(temp).compareTo(needs.get(temp))==0 ){
                    //字符temp出现次数符合要求，count代表符合要求的字符个数
                    count++;
                }
            }
            //优化到不满足情况，right继续前进找可行解
            right++;
            //符合要求的字符个数正好是t中所有字符，获得一个可行解
            while(count==needs.size()){
                //更新结果
                if(right-left<minLen){
                    start=left;
                    end=right;
                    minLen=end-left;
                }
                //开始进行优化，即缩小区间，删除s[left],
                char c=s.charAt(left);
                
                //当前删除的字符包含于t,更新Windows中对应出现的次数，如果更新后的次数<t中出现的次数，符合要求的字符数减1，下次判断count==needs.size()时不满足情况，
                if(needs.containsKey(c)){
                    if(windows.get(c).compareTo(needs.get(c)) == 0){
                        count--;
                    }
                    windows.put(c,windows.getOrDefault(c,1)-1);
                }
                left++;
            }
            
        }
        //返回覆盖的最小串
        return minLen==Integer.MAX_VALUE ? "":s.substring(start,end);
    }
}

leetcode 567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

class Solution {
    public boolean checkInclusion(String t, String s) {

        int left, right, count, minLen = Integer.MAX_VALUE;
        int start = 0, end = 0;

        //needs存储t的<字符,出现次数>,windows存储<s中与t中字符相同的字符,出现次数>
        HashMap<Character, Integer> needs = new HashMap<>();
        HashMap<Character, Integer> windows = new HashMap<>();

        //初始化needs
        for (int i = 0; i < t.length(); i++) {
            //needs.getOrDefault(t.charAt(i),0)+1 含义是：needs如果包含t.charAt(i)，
            //则取出值+1;不包含取0+1
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }

        left = right = count = 0;
        while (right < s.length()) {
            //获取字符
            char temp = s.charAt(right);
            //如果是t中字符，在windows里添加，累计出现次数
            if (needs.containsKey(temp)) {
                windows.put(temp, windows.getOrDefault(temp, 0) + 1);
                //注意：Integer不能用==比较，要用compareTo
                if (windows.get(temp).compareTo(needs.get(temp)) == 0) {
                    //字符temp出现次数符合要求，count代表符合要求的字符个数
                    count++;
                }
            }
            //优化到不满足情况，right继续前进找可行解
            right++;
            //符合要求的字符个数正好是t中所有字符，获得一个可行解
            while (right - left >= t.length()) {
                //更新结果
                if (count == needs.size()) {
                    return true;
                }
                //开始进行优化，即缩小区间，删除s[left],
                char c = s.charAt(left);
                left++;
                //当前删除的字符包含于t,更新Windows中对应出现的次数，如果更新后的次数<t中出现的次数，符合要求的字符数减1，下次判断count==needs.size()时不满足情况，
                if (needs.containsKey(c)) {
                    if (windows.get(c).compareTo(needs.get(c)) == 0) {
                        count--;
                    }
                    windows.put(c, windows.getOrDefault(c, 1) - 1);
                }
            }

        }
        //返回覆盖的最小串
        return false;
    }
}

leetcode 438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

class Solution {

    public List<Integer> findAnagrams(String s,String t) {

        int left, right, count, minLen = Integer.MAX_VALUE;
        int start = 0, end = 0;
        List<Integer> res = new ArrayList();

        //needs存储t的<字符,出现次数>,windows存储<s中与t中字符相同的字符,出现次数>
        HashMap<Character, Integer> needs = new HashMap<>();
        HashMap<Character, Integer> windows = new HashMap<>();

        //初始化needs
        for (int i = 0; i < t.length(); i++) {
            //needs.getOrDefault(t.charAt(i),0)+1 含义是：needs如果包含t.charAt(i)，
            //则取出值+1;不包含取0+1
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }

        left = right = count = 0;
        while (right < s.length()) {
            //获取字符
            char temp = s.charAt(right);
            //如果是t中字符，在windows里添加，累计出现次数
            if (needs.containsKey(temp)) {
                windows.put(temp, windows.getOrDefault(temp, 0) + 1);
                //注意：Integer不能用==比较，要用compareTo
                if (windows.get(temp).compareTo(needs.get(temp)) == 0) {
                    //字符temp出现次数符合要求，count代表符合要求的字符个数
                    count++;
                }
            }
            //优化到不满足情况，right继续前进找可行解
            right++;
            //符合要求的字符个数正好是t中所有字符，获得一个可行解
            while (right - left >= t.length()) {
                //更新结果
                if (count == needs.size()) {
                    res.add(left);
                }
                //开始进行优化，即缩小区间，删除s[left],
                char c = s.charAt(left);
                left++;
                //当前删除的字符包含于t,更新Windows中对应出现的次数，如果更新后的次数<t中出现的次数，符合要求的字符数减1，下次判断count==needs.size()时不满足情况，
                if (needs.containsKey(c)) {
                    if (windows.get(c).compareTo(needs.get(c)) == 0) {
                        count--;
                    }
                    windows.put(c, windows.getOrDefault(c, 1) - 1);
                }
            }

        }
        //返回覆盖的最小串
        return res;
    }
}

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

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

class Solution {
       public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int res = 0; // 记录结果
        Map<Character,Integer> windows = new HashMap();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            windows.put(c, windows.getOrDefault(c, 0) + 1);
            // 判断左侧窗口是否要收缩
            while (windows.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                windows.put(d, windows.getOrDefault(d, 1) - 1);
            }
            // 在这里更新答案
            res = Math.max(res, right - left);
        }
        return res;
    }
}