含K个不同字符的最长子串算法中while能否替换为if的疑问

我正在实现获取含K个不同字符的最长子串的需求。

示例 #

输入：abcbdbdbbdcdabd

• k = 2时，输出为bdbdbbd
• k = 3时，输出为bcbdbdbbdcd
• k = 5时，输出为abcbdbdbbdcdabd

我使用的代码如下：

// Define the character range
public static final int CHAR_RANGE = 128;

// Function to find the longest substring of a given string containing
// `k` distinct characters using a sliding window
public static String findLongestSubstring(String str, int k)
{
    // base case
    if (str == null || str.length() == 0) {
        return str;
    }

    // stores the longest substring boundaries
    int end = 0, begin = 0;

    // set to store distinct characters in a window
    Set<Character> window = new HashSet<>();

    // Count array `freq` stores the frequency of characters present in the
    // current window. We can also use a map instead of a count array.
    int[] freq = new int[CHAR_RANGE];

    // `[low…high]` maintains the sliding window boundaries
    for (int low = 0, high = 0; high < str.length(); high++)
    {
        window.add(str.charAt(high));
        freq[str.charAt(high)]++;

        // if the window size is more than `k`, remove characters from the left
        while (window.size() > k)
        {
            // If the leftmost character's frequency becomes 0 after
            // removing it in the window, remove it from the set as well
            if (--freq[str.charAt(low)] == 0) {
                window.remove(str.charAt(low));
            }

            low++;        // reduce window size
        }

        // update the maximum window size if necessary
        if (window.size() ==k && end - begin < high - low)
        {
            end = high;
            begin = low;
        }
    }

    // return the longest substring found at `str[begin…end]`
    return str.substring(begin, end + 1);
}

public static void main(String[] args)
{
    String str = "abcbdbdbbdcdabd";
    int k = 2;

    System.out.print(findLongestSubstring(str, k));
}

我的疑问是：上述代码中用于调整窗口的while (window.size() > k)循环，我认为每次for循环仅往窗口添加一个字符，添加后立刻判断是否超过k阈值，因此可以直接替换为if(window.size() > k)的条件判断。请问这个修改是否正确？此处使用while循环而非if的原因是什么？

问题解答 #

结论 #

这个修改是错误的，不能将while循环替换为单次if判断。

原因说明 #

虽然每次for循环仅新增1个字符，最多让窗口内的不同字符数量从k变成k+1，但单次移动左边界不一定能将不同字符数量降回k：只有当左边界对应的字符在窗口内的出现次数被减到0时，才会从window集合中移除该字符，真正降低不同字符的计数。如果左边界的字符在窗口中还有剩余的出现次数，单次移动左边界仅会减少它的频率计数，不会改变window的大小。

我们可以举一个简单的反例验证：
假设输入字符串为aaabbb，k=1，期望输出是aaa或者bbb。

• 如果用if判断：当high走到索引3（第一个b）时，window大小变成2，触发if逻辑。此时左边界low=0，freq['a']从3减为2，不等于0，因此不会从window中移除a，low变成1。此时window大小依然是2，后续所有high的遍历都不会触发结果更新，最终输出结果错误。
• 如果用while循环：会持续移动low直到索引3，此时freq['a']被减到0，a被移出window，window大小回到1，循环停止，后续可以正常更新最长子串结果，输出符合预期。

内容的提问来源于stack exchange，提问作者Learner