[Leetcode 3] Longest Substring Without Repeating Characters

原题说明

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
The answer must be a substring, "pwke" is a subsequence and not a substring.

解题思路

这道题需要用一个Hash Table来记录当前字符上一次出现的index, 用一个变量left记录以当前字符结尾的符合题目条件的substring的左侧index. 注意left初始值为-1, 表示以当前字符结尾的符合题目条件的substring的起始位置等于s的起始位置 (index为0).

示例代码 (cpp)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mapping;
        int ret = 0, left = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (mapping.count(s[i])) {
                left = max(left, mapping[s[i]]);
            }
            mapping[s[i]] = i;
            ret = max(ret, i - left);
        }
        return ret;
    }
};

示例代码 (python)

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        iLeft = -1
        ret = 0
        charDict = dict()
        for iRight in range(len(s)):
            if s[iRight] in charDict and charDict[s[iRight]] >= iLeft:
                iLeft = charDict[s[iRight]]
            charDict[s[iRight]] = iRight
            if iRight - iLeft > ret:
                    ret = iRight - iLeft
        return ret

复杂度分析

时间复杂度: O(n) 其中n为s的长度
空间复杂度: O(1) 因为不同字符的数量有限(一般来说为256), 所以mapping的大小是恒定的

归纳总结

这道题中的mapping可以用vector<int>代替unordered_map, 但是作者倾向于使用后者, 因为更有普遍性, 不容易与面试官产生分歧(比如面试官默认s只有26个字母, 那么hard code字符数为256就容易产生分歧), 即使一定要hard code字符数, 也需要和面试官说明.

这道题的思路产生过程并不直接, 面试中如果一下子想不清楚, 建议可以带一个例子, 一步步手动推导结果, 从中或许能够找到一些灵感, 至少也可以让面试官看到思考过程.