无重复字符的最长子串

无重复字符的最长子串

题目说明

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解决方案

本题本人用Python和C++两种方式进行实现,具体实现方式如下:

  1. Python执行方案:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    res = 0
    if s is None or len(s) == 0:
    return res
    d = {}
    tmp = 0
    start = 0
    for i in range(len(s)):
    if s[i] in d and d[s[i]] >= start:
    start = d[s[i]] + 1
    tmp = i - start + 1
    d[s[i]] = i
    res = max(res, tmp)
    return res
  2. C++执行方案:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
    set<char> cache;
    int maxlen = 0;
    int left = 0;
    int index = 0;
    while (index < s.size()) {
    if (cache.find(s[index]) == cache.end()) {
    cache.insert(s[index++]);
    maxlen = max(maxlen, (int)cache.size());
    }
    else {
    cache.erase(s[left++]);
    }
    }
    return maxlen;
    }
    };

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!