LeetCode之Longest Substring Without Repeating Characters 最长无重复子串

àì夳堔傛蜴生んèń 2021-06-10 20:42 256阅读 0赞

## **一、题目** ##

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.

## **二、考虑过程** ##

比如输入jbpnbwwd，首先从头开始统计子字符串，当出现重复字符时，开始下一个子字符串的统计，但是要注意下一个子字符串的统计位置应该是从第一次出现相同字符的下一位开始。

## **三、代码** ##

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
        string ans[2] = {"",""};
        int len[2] = {0,0};
    
        for(unsigned int i=0; i<s.size(); i++){
            string::size_type pos = ans[1].find(s[i]);
            if(pos==string::npos){
                ans[1] += s[i];
                len[1]++;
            }else{
                if(len[0]<len[1]){
                    len[0] = len[1];
                    ans[0] = ans[1];
                }
                len[1] = 0;
                ans[1] = "";
                string::size_type rpos = s.rfind(s[i],i-1);
                i = i - (i-rpos-1);   //这里注意为什么从重复字符的第一个的下一位开始：如果再将位置往前移的话肯定包括了当前的重复字符，只有从下一位才不会同时包含两个相同字符。
                i--;
            }
        }
        if(len[0]<len[1]){
            return len[1];
        }else{
            return len[0];
        }
        }
    };

## **四、另一种** ##

另一种方式：考虑到最大子串要么是整个字符串；要么就是两个相同字符间距离。可以用map存储第一个字符，当出现相同字符时加以判断。  
![这里写图片描述][20161010190612382]  
首先需要明确找不重复字符长度，只需要找到两个相同字符之间（需其中不包含另外两个较小长度相同字符）的最大距离，这就意味着我们可以用map存储字符，当发现有相同的就求其距离。  
![这里写图片描述][SouthEast]  
看上图，在前面几步1，2，3匹配问题不大，只要在找到相同求解距离，更新字符的map就行，但是在第4步，b的匹配中，出现两个字符d被b包含。这是我们直接用map中b的位置相减就会出现问题。这是有个好办法，在代码 if(con.count(s\[i\]))\{ tem = max(tem,con\[s\[i\]\]+1); \}中我们表明已经找到两个d了，这时我们需要用个tem暂时存储前一个d的位置（tem存的是在所有找到的两个字符中前一个字符所在位置最大的），当我们发现前一个b的位置小于tem是就表明有两个d在两个b之间。

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int maxl=0,tem=0;
            unordered_map<char,int> con;
            for(int i=0; i<s.size(); i++){
                if(con.count(s[i])){
                    tem = max(tem,con[s[i]]+1);  //一般情况下，应该时map记录的两个字符间距，但是，如果出现两个相同字符串交叉问题，就要修改一下。
                }
                con[s[i]] = i;
                maxl = max(maxl,i-tem+1);
            }
            return maxl;
        }
    };

[20161010190612382]: /images/20210520/15e1c435390c4486a44449dc0dc6b7b6.png
[SouthEast]: /images/20210520/61a181a6a9b54f2c8829a8b84d6d8144.png