PHP 滑动窗口算法实现计算最长无重复子串

PHP 滑动窗口算法实现计算最长无重复子串

author: he xiaodong date: 2020-06-03
无重复字符的最长子串

这是 LeetCode 第三题,题干如下:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:   输入: “abcabcbb”   输出: 3   解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2:   输入: “bbbbb”   输出: 1   解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示例 3:   输入: “pwwkew”   输出: 3   解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-window-substring

解题思路

1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。重点只是判断新加入字符串有没有在窗口中已存在。

4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

PHP 实现
 /**
  * @param String $s
  * @return Integer
  */
function lengthOfLongestSubstring($s) {
    $left = 0;
    $right = 0;
    $res = 0;
    while ($right < strlen($s)) {
        // $c 是将移入窗口的字符
        $c = $s[$right];
        // 右移窗口
        $right++;
        // 进行窗口内数据的一系列更新
        $window[$c] = isset($window[$c]) ? $window[$c] + 1 : 1;

        // 判断左侧窗口是否要收缩
        while ($window[$c] > 1) {
            // d 是将移出窗口的字符
            $d = $s[$left] ?? '';
            // 左移窗口
            $left++;
            // 进行窗口内数据的一系列更新
            $window[$d]--;
        }

        $res = max($res, $right - $left);
    }

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

return lengthOfLongestSubstring($s = "abcabcbb");  // output: 3

参考链接:

  1. 滑动窗口解题框架思路,强烈推荐这个网站的作者