<< 更多leetcode题目

题目链接

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

难度

中等

介绍

在上一篇易水介绍了自己对这个问题的解决方案，但那个方案执行效率和空间使用都很差。本文主要是介绍 stanislav-iablokov 的滑动窗口解决方案，他的算法时间复杂度为 O(n)，空间复杂度为 O(1)，完全可以用"简洁优雅"这四个字来形容！

C++解决方案

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int max_len = 0;

        // [1] longest substring is the one with the largest 
        //    difference between positions of repeated characters; 
        //    thus, we should create a storage for such positions 
        vector<int> pos(128,0);

        // [2] while iterating through the string (i.e., moving 
        //    the end of the sliding window), we should also 
        //    update the start of the window 
        int start = 0;

        for (int end = 0; end < s.size(); end++)
        {
            auto ch = s[end];

            // [3] get the position for the start of sliding window 
            //    with no other occurences of 'ch' in it 
            start = max(start, pos[ch]);

            // [4] update maximum length 
            max_len = max(max_len, end-start+1);

            // [5] set the position to be used in [3] on next iterations
            pos[ch] = end + 1;
        }

        return max_len;
    }
};

算法分析

stanislav-iablokov的算法，思路正是上一篇中易水提过的想法：最长不重复子串，是两个重复字符之间的最大长度。但当时易水陷入了思维定势，始终想用字符查找、比较解决问题，但没有想到滑动窗口的解决方法。
在此算法中，stanislav-iablokov用 start 表示滑动窗口的起始位置，初始值为 0，后续循环中会将其值设为离起点最远的重复字符所在位置的后面(即其数组下标加1)；end表示滑动窗口的结束位置，初始值为 0，在循环中依次后移；pos[128]数组用于存放每个字母上一次出现过的位置，初始值为0，代表字母没出现过。
在循环中，end会依次后移，然后会检查start是否需要后移：如果出现了重复字符，且重复字符在当前start之后，则将start后移至该重复字符的后面；否则start保持不变。在确定了滑动窗口的起始地址后，计算窗口中字符长度，即为不重复字符的长度，将其最大长度保存至 max_len 变量即可。
算法的精妙之处在于如何确定滑动窗口起始位置：如果在当前start之后存在end位置上的字符，说明在当前start和end间出现了重复字符，此时需要把start后移至重复字符的后面。移动之后，在start和end之间就不存在重复字符了。
另外，这个算法还打破了易水的思维定势，程序中完全没有用到字符查找、字符比较，而是用数组下标代之！
易水画了一副示意图，展示了该算法对于字符串 pwkwew 的处理过程：

总结

以后在遇到下面这类问题时，可以考虑滑动窗口方案：

• 给定一个序列，例如数组、字符串；
• 需要处理的数据是其中的一个子序列或子字符串；
• 给定了一个固定的窗口大小，或是要求找出窗口的大小(例如本题)；

使用滑动窗口方案，关键在于窗口起点和终点的确定，这需要根据问题进行具体分析。

<< 更多leetcode题目

题目链接

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

难度

中等

C++解决方案

class Solution {
public:
    // 计算从位置 start 开始不重复字符的最大长度
    int uniqueChars(string s, int start)
    {
        int len = 0;
        vector<char> chars;
        for (int i = start; i < s.size(); i++)
        {
            char c = s[i];
            // 检查此字符是否在前面出现过
            if (find(chars.begin(), chars.end(), c) == chars.end())
            {
                chars.push_back(c);
                len++;
            }
            else
            {
                break;
            }
        }

        return len;
    }

    int lengthOfLongestSubstring(string s) {
        int m = 0;
        // 依次遍历每个字符，计算最大长度
        for (int i = 0; i < s.size(); i++)
        {
            int len = uniqueChars(s, i);
            m = max(m, len);
        }

        return m;
    }
};

解题思路

如果只是要实现这道题目的要求，难度并不大。 易水的上述实现方案采用的是最笨的方法：遍历字符串，从某一位置开始、计算其后不重复字符的最大长度。

总结

上述方式虽然能实现功能，但此方法的时间复杂度为 O(n^2)，空间复杂度为 O(n)，执行效率和空间使用都比较差。事实也证明了这一点，这是 leetcode.com 对我的算法给出的评价：

Runtime: 819 ms, faster than 9.07% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 335.7 MB, less than 5.39% of C++ online submissions for Longest Substring Without Repeating Characters.

运行时间只超过了 9% 的 C++ 实现方案，而内存使用只比 5% 的 C++ 方案节省内存！
接下来易水尝试优化算法，当时闪过一个想法，所谓的“最长不重复子串”，可以定义为两个重复字符之间的最大长度，但易水在把这个想法转换为算法时遇到了障碍，始终无法摆脱字符查找、比较的思维定势，因此一直找不到更优解决方案。直到在评论区看到stanislav-iablokov的解法，才惊叹于他的实现方案之简洁优雅，我将在下一篇介绍他的解决方案，这一方案所采用的思路，正是易水上面提到的想法！