借助map辅助,用map记录每一个字符的最大的下标,用left记录没有重复字符子串的起始位置,空间复杂度和时间复杂度均为O(n)。

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        // write code here
        int size = s.size();
        if (size < 1) return 0;
        unordered_map<char, int> um;
        int maxLen = 0, left = 0;       // left记录上一个没有重复的位置
        for (int i = 0; i < size; ++i) {
            if (um.find(s[i]) != um.end()) {    // 如果在map里
                left = max(left, um[s[i]] + 1);
            }
            maxLen = max(maxLen, i - left + 1);
            um[s[i]] = i;
        }
        return maxLen;
    }
};