LeetCode - Longest Substring Without Repeating Characters

写在前面

ac一道找找状态

思路

只需要给出无重复的最大字符串长度, 而不用输出字符串内容; 该长度的字符串可以不止一个

遍历一次输入字符串, 遍历时更新无重复的子字符串, 比较子串和目前最大无重复串的长度, 决定是否更新最大无重复子串

解答

存在测试用例: 字符串为空

第一版

1. 使用curStart和curEnd定位当前无重复子串
   
2. 使用max保存当前最大无重复子串
   
3. 若在当前子串中查找到重复字符, 其下一位置作为子串的新起点
   
4. 增加当前子串长度时, 已纳入当前字符
   

使用左开右闭区间 [curStart, curEnd) 描述当前无重复子串

Copy 1class Solution {
 2public:
 3    int lengthOfLongestSubstring(string s) {
 4        auto n = s.size();
 5        int curStart = 0, curEnd = 1;
 6        string max = s.substr(0, 1);
 7
 8        for (; curEnd < n; ++curEnd)
 9        {
10            auto res = s.substr(curStart, curEnd - curStart).find(s[curEnd]);
11
12            if (res != string::npos)
13            {
14                curStart += res + 1;
15            }
16            else 
17            {
18                if (curEnd + 1 - curStart > max.size())
19                {
20                    max = s.substr(curStart, curEnd + 1 - curStart);
21                }
22            }
23        }
24        return max.size();
25    }
26};

优化点

1. 字符串查找可使用无序容器
   
2. 只需要最大无重复字符串的长度, 无需保存其内容
   
3. substr的处理包容了字符串为空的情形
   

第二版

1. 使用unordered_map: 移除无效字符
   

   Copy 1class Solution {
    2public:
    3    int lengthOfLongestSubstring(string s) {
    4        auto n = s.size();
    5        unordered_map<char, int> um;
    6        int start = 0, max = 0;
    7
    8        for (auto i = 0; i < n; ++i)
    9        {
   10            auto res = um.find(s[i]);
   11            if (res != um.end())
   12            {
   13                for (auto j = start; j < res->second; ++j)
   14                {
   15                    um.erase(s[j]);
   16                }
   17
   18                start = res->second + 1;
   19                res->second = i;
   20            }
   21            else 
   22            {
   23                um.insert({s[i], i});
   24                if (um.size() > max)
   25                {
   26                    max = um.size();
   27                }
   28            }
   29        }
   30        return max;
   31    }
   32};

2. 使用unordered_set
   
   当集合中存在当前字符时, 先于字符加入集合的需要删除, 后于字符加入集合的则保留, 无明显的手段判断先后顺序
   

   选择遍历字符串, 从前往后删字符, 如果不再查找得到, 则刚刚好删除了包括该字符在内的所有前缀
   

   Copy 1class Solution {
    2public:
    3    int lengthOfLongestSubstring(string s) {
    4        auto n = s.size();
    5        unordered_set<char> us;
    6        int start = 0, max = 0;
    7
    8        for (auto i = 0; i < n; ++i)
    9        {
   10            if (us.find(s[i]) != us.end())
   11            {
   12                do {
   13                    us.erase(s[start++]);
   14                } while (us.find(s[i]) != us.end());
   15
   16                us.insert(s[i]);
   17            }
   18            else 
   19            {
   20                us.insert(s[i]);
   21                if (us.size() > max)
   22                {
   23                    max = us.size();
   24                }
   25            }
   26        }
   27        return max;
   28    }
   29};

3. 使用unordered_map: 更新下标
   
   判断字符重复的标准为: 已有关键字, 且在当前子串序列中
   

   Copy 1class Solution {
    2public:
    3    int lengthOfLongestSubstring(string s) {
    4        auto n = s.size();
    5        unordered_map<char, int> um;
    6        int start = 0, maxLen = 0;
    7
    8        for (int i = 0; i < n; ++i)
    9        {
   10            if (um.count(s[i]) && um[s[i]] >= start)
   11            {
   12                start = um[s[i]] + 1;
   13                um[s[i]] = i;
   14
   15            }
   16            else
   17            {
   18                um[s[i]] = i;
   19                maxLen = max(maxLen, i + 1 - start);
   20            }
   21        }
   22        return maxLen;
   23    }
   24};