LongestSubstringWithoutRepeatingCharacters

题目

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

解题报告

理解题意

• 给定一个字符串，求最长的无重复字符的子串
• 子串：没有重复的字符
• 子串长度：右边-左边

理解例子

例子 1

• 输入：abcabcbb
• 输出：3
• 最长的子串：abc/bca/cab 长度为 3

思路

• 题目要求计算最长子串长度，并且是无重复的子串。
• 字符串的长度的计算：当前位置-开始位置
• 那么随后的问题就是如何计算开始位置。
• 如果没有重复子串出现过，那么开始位置就是0，如果重复子串出现过，那么开始位置就是这个位置的下一个位置。
• 需要一个数据结构来记录每一个字符上一次出现的位置

流程

• 遍历整个字符串
• 针对每一个字符，在合适的时候更新left，那么剩下的问题就是何时更新left
• 针对每一个字符，计算并保存最大的长度
• 遍历完成后返回最大的长度
• 时间复杂度：线性时间 \(\mathcal{O(n)}\)

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
       if (s.empty()) return 0;
        vector<int> pos_map(256, -1);
        int start = 0, ans = 0;
        for (int i = 0; i < s.length(); i++) {
            start = max(pos_map[s[i]]+1, start);
            pos_map[s[i]] = i;
            ans = max(ans, i - start+1);
        }
        return ans;
    }
};

时间复杂度

如一开始分析：时间复杂度：线性时间 \(\mathcal{O(n)}\)

空间复杂度

额外申请了和一个链表，因此空间复杂度也为 \(\mathcal{O(max(len(l1), len(l2)))}\)