滑动窗口算法详解：如何求解字符串的最短子串问题

滑动窗口算法详解：如何求解字符串的最短子串问题

引用

CSDN

1.

https://blog.csdn.net/m0_70871140/article/details/144201034

在编程领域，字符串问题是一个经典的研究方向，既涉及算法优化，也考验编码实现能力。在众多问题中，寻找字符串的最短子串问题是一道具有实际意义的题目。它不仅在面试中常见，而且其解决方法在文本处理、数据分析等场景中应用广泛。本文将深入解析这一问题，并详细介绍如何利用滑动窗口算法实现高效解法。

一、问题描述

任务：给定一个仅由小写英文字母组成的字符串，找到其最短的子串，要求这个子串必须包含输入字符串中出现过的所有不同字符。

输入：

• 一个长度不超过 200 的字符串，仅由小写英文字母组成。

输出：

• 满足条件的最短子串。如果存在多个解，输出其中最靠左的子串。

示例：

• 输入：
  adfasjdoiasdfa
• 输出：
  fasjdoi

二、问题分析

1. 任务拆解：

• 首先，需要找到输入字符串中的所有不同字符。
• 然后，动态追踪某个子串是否包含了所有这些字符。
• 最后，输出满足条件的最短子串。

2. 挑战点：

• 如何高效地统计当前子串中所有字符的频次。
• 在满足条件的情况下，如何动态缩短子串以找到最短解。

3. 解法思路：

• 本问题需要快速调整子串范围，以避免暴力枚举所有子串带来的性能问题。
• 滑动窗口是一种高效的解决方案，它通过动态调整窗口边界，在一次遍历中完成任务。

三、解法：滑动窗口

滑动窗口算法是一种巧妙解决子串问题的方法，通过两个指针（left和right）表示窗口的起止位置，动态调整窗口大小，以满足特定条件。以下是详细的步骤：

步骤 1：初始化变量

• 用left和right两个指针表示窗口的左右边界，初始值均为0。
• 用一个Map（哈希表）存储当前窗口中每个字符的频次。
• 用minLen记录当前满足条件的最小子串长度，result保存最终结果。

步骤 2：右指针扩展窗口

• 每次移动右指针，将当前字符加入窗口。
• 更新哈希表，增加该字符在窗口中的频次。

步骤 3：左指针收缩窗口

• 当窗口中包含所有目标字符时，尝试移动左指针缩小窗口。
• 每次移动左指针时，检查当前窗口是否仍然满足条件：
• 如果满足，则更新结果为当前子串；
• 如果不满足，则停止收缩。

步骤 4：返回结果

• 当右指针遍历完字符串后，返回记录的最短子串。

四、代码实现

以下是基于上述思路的 Java 实现：

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class No19 {
    public static String solution(String str) {
        int left = 0, right = 0; // 初始化窗口边界
        String result = ""; // 保存最短子串结果
        Map<Character, Integer> map = new HashMap<>(); // 存储窗口内字符频次
        // 初始化目标字符集合
        for (char c : str.toCharArray()) {
            map.put(c, 0);
        }
        
        int uniqueCharCount = map.size(); // 目标字符的总数
        int minLen = Integer.MAX_VALUE; // 初始化最小长度为最大值
        
        while (right < str.length()) {
            char c = str.charAt(right);
            map.put(c, map.getOrDefault(c, 0) + 1); // 更新当前字符频次
            // 如果窗口包含所有目标字符，则尝试缩小窗口
            while (map.values().stream().allMatch(count -> count > 0)) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    result = str.substring(left, right + 1); // 更新结果
                }
                // 收缩窗口：减少左边字符的频次
                char leftChar = str.charAt(left);
                map.put(leftChar, map.get(leftChar) - 1);
                left++;
            }
            right++; // 扩展窗口
        }
        
        return result;
    }
    public static void main(String[] args) {                          
        System.out.println(Objects.equals(solution("adfasjdoiasdfa"), "fasjdoi"));
    }
}

五、代码解析

1. 初始化目标字符：

for (char c : str.toCharArray()) {
    map.put(c, 0);
}

将所有字符初始化为频次为0，这确保我们可以直接更新窗口中字符的频次，而无需反复判断字符是否已出现。

2. 动态调整窗口

• 扩展窗口：

map.put(c, map.getOrDefault(c, 0) + 1);

通过右移指针，将当前字符加入窗口。

• 收缩窗口：

map.put(leftChar, map.get(leftChar) - 1);
left++;

判断窗口是否满足条件，满足时通过左移指针尝试缩小窗口。

3. 更新结果

if (right - left + 1 < minLen) {
    minLen = right - left + 1;
    result = str.substring(left, right + 1);
}

记录满足条件的最短子串，同时确保是最靠左的解。

六、时间复杂度分析

• 初始化目标字符：需要遍历一次字符串，时间复杂度为 O(n)。
• 滑动窗口调整：每个指针最多遍历整个字符串一次，总体复杂度为 O(n)。
• 判断条件：map.values().stream().allMatch(...)的复杂度为 O(1)，因为目标字符的数量是有限的（最多 26 个小写字母）。

总时间复杂度为 O(n)。

七、总结与拓展

滑动窗口是一种高效解决子串或子数组问题的算法，尤其适合处理动态窗口大小的问题。本题通过滑动窗口巧妙调整子串范围，达到了高效计算的目标。总结几点收获：

1. 问题拆解能力

• 通过明确需求，合理分解任务，确保算法实现简单清晰。

2. 数据结构选择

• 使用Map（哈希表）统计字符频次，提升了字符操作的效率。

3. 滑动窗口优化

• 通过动态调整窗口边界，避免了暴力枚举带来的性能开销。