0003._Longest_Substring_Without_Repeating_Characters.md

3. Longest Substring Without Repeating Characters

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/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 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

用 map储存 key为字符，value 为这个字符的位置，我们可以维护一个子字符串(无重复字符)，记录它的起始位置，遍历 string s 当无法在map中找到字符或者小于子字符串的起始位置，就是没有在这个字符串中出现，反之则字符重复，不过 map查找为 O(lgn)，因此总的时间复杂度为O(NlgN)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    map<int,int> m;
    int beg = 0,length = s.length(),ll = 0,ans = 0;
    for(int i = 0;i < length;++i)
    {
        if(m.find(s[i]) == m.end() || m[s[i]] < beg)
            ll++;
        else
        {
            int pos = m[s[i]];
            ans = max(ll,ans);
            ll = ll - (pos - beg);
            beg = pos + 1;
        }
        m[s[i]] = i;
    }
    ans = max(ans,ll);
    return ans;
    }
};

思路 2 - 时间复杂度: O(NlgN)- 空间复杂度: O(1)******

这个思路和上面差不多，用到了一个小窍门，因为储存的是字符，char为8位，因此能储存的最大数为256，这样空间复杂度就为O(1)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int m[256];
    for(int i = 0;i < 256;++i)
        m[i] = -1;
    int beg = 0,length = s.length(),ll = 0,ans = 0;
    for(int i = 0;i < length;++i)
    {
        if(m[s[i]] < beg)
            ll++;
        else
        {
            int pos = m[s[i]];
            ans = max(ll,ans);
            ll = ll - (pos - beg);
            beg = pos + 1;
        }
        m[s[i]] = i;
    }
    ans = max(ans,ll);
    return ans;
    }
};