Longest Substring Without Repeating Characters

每日算法——letcode系列

问题 Longest Substring Without Repeating Characters

Difficulty: Medium

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};

翻译

无重复字符的最长子串

难度系数：中等

给定一个字符串，找其无重复字符的最长子串的长度。

例如： "abcabcbb"的无重复字符的最长子串是"abc"，长度为3。 "bbbbb"的无重复字符的最长子串是"b"，长度为1

思路

方案一：

遍历字符串，如果前面有重复的，就把前面离现在这个字符最近的重复的字符的索引记录在repeatIndex, 如果没有重复，则也为repeatIndex。
注意： 当前的repeatIndex要大于以前记录的repeatIndex，小于则不更新repeatIndex下面第三种情况

如：
"abcabcbb" -> $\frac{abcabcbb}{00012357}$ -> $\frac{12345678}{00012357}$ -> 3

"bbabcdb" -> $\frac{bbabcdb}{0112224}$ -> $\frac{1234567}{0112224}$ -> 4

"abba" -> $\frac{abba}{0022}$ -> $\frac{1234}{0022}$ -> 2

方案二：

找重复的时候可以用hashmap的方法来降低时间复杂度, string的字符为key, 索引为value。

代码

方案一：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int repeatIndex = 0;
        int size = static_cast<int>(s.size());
        
        for (int i = 0; i < size; ++i){
            for (int j = i - 1; j >= 0; --j) {
                if (s[i] == s[j]){
                    if (j > repeatIndex){
                    repeatIndex = j;
                    }
                    break;
                }
            }
            if (maxLen < i -repeatIndex){
                maxLen = i - repeatIndex;
            }
        }
        return maxLen;
    }
}

方案二：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int repeatIndex = 0;
        int size = static_cast<int>(s.size());
        map<char, int> tempHash;
        for (int i = 0; i < size; ++i){
            if (tempHash.find(s[i]) != tempHash.end() && tempHash[s[i]] > repeatIndex){
                repeatIndex = tempHash[s[i]];
            }
            if (maxLen < i -repeatIndex){
                maxLen = i - repeatIndex;
            }
            tempHash[s[i]] = i;
        }
        return maxLen;
    }
}