找到最小窗口子字符串 - leetcode - 解决方案不起作用

Question

给定一个字符串 S 和一个字符串 T，找到 S 中包含 T 中所有字符的最小窗口，复杂度为 O(n)。

例子：

输入：S =“ADOBECODEBANC”，T =“ABC”输出：“BANC”

我努力尝试使用滑动窗口技术提出解决方案，但我被困在这里。有人可以帮忙吗？

    package com.tryPrep.Strings;

import java.util.HashMap;

public class MinWindowSubstring {

    static String minWinSubStr(String s, String t){

        HashMap<Character, Integer> tabl = new HashMap<>();

        for(char c: t.toCharArray()){

            int charCount=0;

            if(tabl.containsKey(c))

              charCount = tabl.get(c);

            tabl.put(c, charCount+1);

        }

        int begin =0, end =0, counter=tabl.size();

        String ans="";

        int max=s.length();

        while(end < s.length()) {

            char endChar = s.charAt(end);

            if (tabl.containsKey(endChar)) {

                int charCount = tabl.get(endChar);

                if (charCount > 0) {

                    counter--;

                    tabl.put(endChar, charCount - 1);

                }

            }

            end++;

            while (counter == 0) {

                if (max > end - begin) {

                    ans = s.substring(begin, end - begin);

                    max = ans.length();

                }

                char beginChar = s.charAt(begin);

                if (tabl.containsKey(beginChar)) {

                    int charCount = tabl.get(beginChar);

                    if(charCount == 0) {

                        tabl.put(beginChar, charCount + 1);

                        counter++;

                    }

                }

                begin++;

            }

        }

        return ans;

    }

    public static void main(String[] args) {

        String s = "ADOBECODEBANC";

        String t = "ABC";

        System.out.println("minWinSubStr M1 : " + minWinSubStr(s, t));

    }

}

输出 ：

minWinSubStr M1 : ADOBEC

我看到当 end 达到字符串长度时循环得到满足，但计数器仍然不为 0。您能指出是什么问题来解锁我吗？

Answer 1

问题是当您在删除 A（索引 0 处）后增加计数器时。你开始寻找另一个A来弥补这一损失。ADOBECODEBANC&nbsp;^&nbsp; &nbsp; &nbsp; &nbsp; ^begin&nbsp; &nbsp; end当您这样做时，您的代码不知不觉地没有考虑 B（在索引 9 处），并且结束指针到达了 A（在索引 10 处）。之后，当开始指针到达 B （索引 4 处）并且您递增计数器时，您的结束指针无法找到任何其他 B。ADOBECODEBANC&nbsp; &nbsp; ^&nbsp; &nbsp; &nbsp;^&nbsp; begin&nbsp; end因此你得到的答案是ADOBEC当结束指针找到必须考虑的任何字符时，您可以做些什么来纠正，删除该字符的第一个索引并添加最近遇到的索引。一旦完成，当开始指针遇到该字符时，您可以轻松忽略该字符，因为该字符的频率不会影响。这是有效的，因为我们想要从开始而不是从末尾缩小窗口。在您的情况下，每次结束指针遇到tabl中的任何字符时，您都可以减少计数器。现在，当开始指针遇到任何值为负的字符时，不要增加计数器，只需将值加一即可。另外，您应该从头到尾打印值。s.substring(begin, end)考虑当 begin = 8 和 end = 10 时的情况s.substring(8, 10), not s.substring(8, 2)static String minWinSubStr(String s, String t) {&nbsp; &nbsp; System.out.println(s);&nbsp; &nbsp; System.out.println(t);&nbsp; &nbsp; HashMap<Character, Integer> tabl = new HashMap<>();&nbsp; &nbsp; for (char c : t.toCharArray()) {&nbsp; &nbsp; &nbsp; &nbsp; int charCount = 0;&nbsp; &nbsp; &nbsp; &nbsp; if (tabl.containsKey(c))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; charCount = tabl.get(c);&nbsp; &nbsp; &nbsp; &nbsp; tabl.put(c, charCount + 1);&nbsp; &nbsp; }&nbsp; &nbsp; int begin = 0, end = 0, counter = tabl.size();&nbsp; &nbsp; String ans = "";&nbsp; &nbsp; int max = s.length();&nbsp; &nbsp; while (end < s.length()) {&nbsp; &nbsp; &nbsp; &nbsp; char endChar = s.charAt(end);&nbsp; &nbsp; &nbsp; &nbsp; if (tabl.containsKey(endChar)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int charCount = tabl.get(endChar);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (charCount > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tabl.put(endChar, charCount - 1);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; end++;&nbsp; &nbsp; &nbsp; &nbsp; while (counter == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (max > end - begin) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ans = s.substring(begin, end);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = ans.length();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; char beginChar = s.charAt(begin);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (tabl.containsKey(beginChar)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int charCount = tabl.get(beginChar);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(charCount < 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tabl.put(beginChar, charCount + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (charCount == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; tabl.put(beginChar, charCount + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; begin++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return ans;}突出显示我更改的部分。注意：此代码仅解决您的用例，不应在所有测试用例上提供 AC。