[刷题笔记]LeetCode3. Longest Substring Without Repeating Characters

发表于 | 分类于

Descripition

Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，找出不包含重复字符的最长子串

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析

看完题目比较直观的想法，是在遍历字符串的时候，记录从当前位置往前看所能组成非重复子串的最大长度，然后动态更新全局的最大子串长度。

这就需要设置两个指针start和end，用来记录子串的两个端点位置，遍历过程中不断右移end指针，同时更新start指针的位置，使其包含的部分符合非重复子串的定义，每走一步就与全局最大子串长度比较一次，这样达到更新全局最大子串长度的目的。

这就涉及到一个问题，start指针在何时更新，如何更新？

很自然能想到使用一个map来记录每个字符出现的位置，当end指针扫描到的字符在map中存在记录时（假设对应位置为pos），表示符合条件的子串必定包含在pos和end之间，此时可以取start = pos + 1，以使子串长度最大化。不过这里要注意一个问题，start指针是不能向左更新的，因为start指针左移就意味着将之前步骤已经排除在外的部分又重新包含到当前子串中了。

举个例子：考虑字符串abba，起始时start和end都指向第一个字符a；当end扫描到第三个字符b时，此时start仍指向第一个位置，map中已经存储了两个记录map[a]=0和map[b]=1，此时发现b的位置记录1，因此将start指向1+1=2的位置，并更新map[b]=2；end继续扫描到第四个字符a时，再次发现a的位置记录0，此时若直接将start更新为0+1=1，会造成start和end包含的子串bba中出现重复的字符b。

So，综合起来就是end一直往后扫，当发现end指针所指向的内容在map中存在位置记录pos，并且pos >= start时，将start更新为pos+1，每遍历一步就记录一下map的最新内容，同时获得当前子串的长度s = end - start + 1，对比一下maxlen和s的大小并更新maxlen = max(maxlen, s)就行了。哎，说得有点绕，还是写代码清晰啊

该方法只需遍历一次字符串，但须要额外资源存储下标记录，因此时间复杂度和空间复杂度均为O(n)。

C++ Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen = 0;                     // 记录最大子串长度
        int start = 0, end = 0;             // 记录子串两个端点位置
        unordered_map<char, int> pos_map;   // 记录字符最新位置
        
        for (; end < s.size(); ++end)
        {
            char c = s[end];
            if ((pos_map.find(c) != pos_map.end()) &&
                (pos_map[c] >= start))              
            {   // 仅当重复字符的位置在原start右边时才需要更新
                start = pos_map[c] + 1;
            }
            maxlen = max(maxlen, end - start + 1);  // 更新最大长度
            pos_map[c] = end;                       // 记录字符最新位置
        }
        return maxlen;
    }
};