最短覆盖子串

爱被打了一巴掌 2022-10-29 07:55 168阅读 0赞

/** * 给两个字符串S和T，请在S中找到包含T中全部字符的最短子串 */
    public class Solution { 
    
        public static void main(String[] args) { 
            String s = "ebbancf";
            String t = "abc";
            System.out.println(minWindow(s, t));
        }
    
        static String minWindow(String s, String t) { 
            Map<Character, Integer> need = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
            for (int i = 0; i < t.length(); i++) { 
                char c = t.charAt(i);
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
    
            int left = 0;
            int right = 0;
            int valid = 0;
            // 记录最小覆盖子串的起始索引和终止索引
            int start = 0;
            int end = 0;
            while (right <  s.length()) { 
                // r是将加入窗口的字符
                char r = s.charAt(right);
                // 窗口内数据进行一系列更新
    
                //如果r字符存在于need中
                if (need.get(r) != null) { 
                    // 那么把r加入到window中,如果window中已经有r了，那么+1
                    window.put(r, window.getOrDefault(r, 0) + 1);
                    if (window.get(r) == need.get(r)) { 
                        // 把窗口中满足need条件的字符个数+1
                        valid++;
                    }
                }
    
                //右移窗口
                right++;
                //判断左侧窗口是否需要收缩
                while(valid == need.size()) { 
                    //l是将要移出窗口的字符
                    char l = s.charAt(left);
                    // 窗口内数据的一系列更新
                    // 更新最小覆盖子串
                    start = left;
                    end = right;
    
                    if (need.get(l) != null) { 
                        if (window.get(l) == need.get(l)) { 
                            valid--;
                        }
                        window.put(l, window.getOrDefault(l, 0) - 1);
                    }
    
    
                    //左移窗口
                    left++;
                }
    
            }
            return s.substring(start, end);
        }
    }