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

题解：

输入一个字符串，求这个字符串中，不包括重复元素的最大的子串的长度；
例如对于输入："zffcool"
子串为：
"z", "zf", "zff", "zffc", "zffco", "zffcoo","zffcool"；
"f", "ff", "ffc", "ffco", "ffcoo","ffcool"；
"f", "fc", "fco", "fcoo","fcool"；
"c", "co", "coo","cool"；
"o", "oo","ool"；
"o", "ol"；
"l"；
则加粗的为不包含重复字符的子串；
最长的子串为fco，长度为3；输出3；

分析：

image.png

两个指针，begin 指向子串的头，i 向后滑动；
当滑到字符曾出现过时，判断重复的字符是否在子串中，在的话更新 begin，让它指向重复字符的下一个字符，同时更新重复字符的位置；否则，在 begin 的前面，说明子串中没有与当前字符重复的字符，直接更新该重复字符（key）对应的当前位置（value）即可；最后输出最大的子串长度；

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0) {
            return 0;
        }
        map<char, int> hash_map;
        vector<int> result;
        int count = 0;
        int begin = 0;
        for (int i = 0; i < s.length(); i++) {
            if (hash_map.find(s[i]) == hash_map.end()) {
                hash_map.insert(map<char, int>::value_type(s[i], i));
                count += 1;
                result.push_back(count);
            }
            else {
                if (begin > hash_map[s[i]]) {
                    count += 1;
                }
                else {
                    count = count - (hash_map[s[i]] + 1 - begin) + 1;
                    begin = hash_map[s[i]] + 1;
                }
                hash_map[s[i]] = i;
                result.push_back(count);
            }
        }
        return *max_element(result.begin(), result.end());
    }
};

int main() {
    Solution s;
    printf("\"abcabcbb\"：%d\n", s.lengthOfLongestSubstring("abcabcbb"));
    printf("\"bbbbb\"：%d\n", s.lengthOfLongestSubstring("bbbbb"));
    printf("\"pwwkew\"：%d\n", s.lengthOfLongestSubstring("pwwkew"));
    printf("\"\"：%d\n", s.lengthOfLongestSubstring(""));
    printf("\"nfpdmpi\"：%d\n", s.lengthOfLongestSubstring("nfpdmpi"));
    printf("\"nffdmpn\"：%d\n", s.lengthOfLongestSubstring("nffdmpn"));
    printf("\"aabaab!bb\"：%d", s.lengthOfLongestSubstring("aabaab!bb"));
    return 0;
}

结果

"abcabcbb"：3
"bbbbb"：1
"pwwkew"：3
""：0
"nfpdmpi"：5
"nffdmpn"：5
"aabaab!bb"：3

My Solution1:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        count, ss = [0], ''
        for i in range(len(s)):
            if s[i] in ss:
                ss = ss[ss.index(s[i])+1: ] + s[i]
                count.append(len(ss))
            else:
                ss += s[i]
            if len(ss) > 0:
                count.append(len(ss))
        return max(count)

My Solution2:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """        
        if s == '':
            return 0
        begin, long_s, result = 0, '', 0
        for end in range(len(s)):
            if long_s.find(s[end]) == -1:
                long_s += s[end]
                if result < len(long_s):
                    result = len(long_s)
            else:
                begin = long_s.find(s[end]) + 1
                long_s = long_s[begin: ] + s[end]
        return result
  

Reference (转):

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        start = maxLength = 0
        usedChar = {}
        
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)

            usedChar[s[i]] = i

        return maxLength