3. Longest Substring Without Repeating Characters，最长无重复字符子串

Last Updated: 2024-06-14 22:49:28 Friday

-- TOC --

题目分析
直觉One Pass
- Python
- C++
- C
Sliding Window
- Python
- C++
- C

题目分析

Given a string s, find the length of the longest substring without repeating characters.

输入一个字符串，找出最长无重复子串的长度！

Constraints:

0 <= s.length <= 50000

s consists of English letters, digits, symbols and spaces.

示例：

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

pwke只是subsequence，不是substring。注意英语subsequence和substring的区别！

直觉One Pass

将输入字符串一个个拿出来，每拿出来一个，就跟前面已经拿出来的进行比较，此时可发现是否有重复的字符。当存在重复字符的时候，更新代码中的状态信息，然后从重复位置的下一个位置开始，继续拿出字符比较。此过程中，保存最长的长度信息，用于return。注意循环退出后的size可能是最大的。

时间复杂度：\(O(n)\)
空间复杂度：\(O(n)\)

Suppose we are checking the ith char in string s. The maximum number of char which needs to be checked is i-1. So, the worst case time complexity is order of n^2. But if the ckeck action is by hashing instead of one by one, in this implementation, the time complexity is order of n.

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ss = []
        maxlen = 0
        for c in s:
            if c not in ss:
                ss.append(c)
                continue
            maxlen = max(maxlen, len(ss))
            ss = ss[ss.index(c)+1:]
            ss.append(c)
        return max(maxlen, len(ss))

Python的append更快：

# slow
a = [1,2,3] + [4]
# fast
a = [1,2,3]
a.append(4)

要在尾部添加的元素只有1个，没有必要做两个list的合并！

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string ss;
        size_t maxlen {};
        size_t p;
        for(auto c: s){
            if((p=ss.find(c)) == string::npos){
                ss += c;
                continue;
            }
            maxlen = max(maxlen, ss.size());
            ss = ss.substr(p+1);
            ss += c;
        }
        return (int)max(maxlen, ss.size());
    }
};

C

int lengthOfLongestSubstring(char *s){
    char ss[256] = {};
    unsigned char idx = 0; // also size
    char *p;
    int maxlen = 0;
    while(*s){
        if((p=memchr(ss,*s,idx)) == NULL){
            ss[idx++] = *s++;
            continue;
        }
        maxlen = maxlen<idx ? idx : maxlen;
        idx = idx - (p-ss+1);
        memmove(ss, p+1, idx);  // cannot use memcpy
        ss[idx++] = *s++;
    }
    return maxlen<idx ? idx : maxlen;
}

经典的*s++，先取值，然后指针+1。
只能使用memmove，因为overlapping。（memcpy与memmove）
虽然没有Python的str对象，也没有C++的string对象，C语言啥不能造出来！
idx类型是unsigned char，在与maxlen计算时，会被promote为int，其实定义为int类型也没问题，主要是ss的长度只有256。

C语言中，type决定如何解释内存，请看如下示例：

#include <stdio.h>
#include <string.h>

int main(void) {
    char p[] = {0xAA};
    printf("%d\n", *p);
    printf("%d\n", *(unsigned char*)p);

    char a = 129;
    printf("%d\n", a);
    printf("%d\n", (unsigned char)a);
    return 0;
}

输出：

Sliding Window

使用Sliding Window，一般就是记录Window的两端的index，通过两个index的变量，sliding...

前面所用算法，与Sliding Window无本质区别，不同点在与，没有记录两端的index，而是直接记录下全部substring，以此来计算window size。但如果使用sliding window，需记录下substring中字符以及它们最后出现的index，计算上会稍微简单一点点，特别是对C语言，也许代码能够更快，无需更新substring信息。

另一个关键点是查找。每次取一个char都需要查找，如果用hash的方式保存sliding window中的char，查找速度就上去了。

Python

用dict对象来实现membership checking，我的经验是，只比set稍微慢一丢丢。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ss = {}
        maxlen = left = 0
        right = -1  # in case s is empty
        for right,c in enumerate(s):
            if c in ss and ss[c]>=left:
                maxlen = max(maxlen, right-left)
                left = ss[c] + 1
            ss[c] = right
        return max(maxlen, right-left+1)

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> ump;
        ump.reserve(128);
        int lo {};
        int hi {};
        int maxlen {};
        for(; hi<static_cast<int>(s.size()); ++hi){
            char c = s[hi];
            if(ump.contains(c) && ump[c]>=lo){
                maxlen = max(maxlen, hi-lo);
                lo = ump[c] + 1;
            }
            ump[c] = hi;
        }
        return max(maxlen, hi-lo);
    }
};

C++只有unordered_map才能与Python的dict媲美...

C

int lengthOfLongestSubstring(char *s){
    int idxmap[256];
    memset(idxmap, 0xFF, sizeof(int)*256);
    int left, right, maxlen;
    left = right = maxlen = 0;
    while(*s){
        if(idxmap[*s] >= left){
            maxlen = maxlen<(right-left)?(right-left):maxlen;
            left = idxmap[*s] + 1;
        }
        idxmap[*s++] = right++;
    }
    return maxlen<(right-left)?(right-left):maxlen;
}

idxmap[256]的类型需要为int，我在这里犯了错误，这里记录的是每个符号最后出现的index，类型为char是个错误。
全F，就是-1。

本文链接：https://cs.pynote.net/ag/leetcode/202211091/

-- EOF --

-- MORE --