LeetCode_Python(3)_无重复字符的最长子串

需求

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

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

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

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

解决思路

方法一

1. 遍历字符串
   字符未重复时拼接到中间字符串中，出现重复字符时，先将中间字符串追加到中间结果list中；
   在中间字符中找到重复字符的位置，从下一位开始截取后面的字符串，与重复字符拼接，重新赋值为中间字符串，继续下次遍历;
2. 遍历完成后，需要将最后一个中间字符串添加到中间list中，这一步很容易被忽略；
3. 最后通过生成器表达式结合max()函数，返回中间结果list中元素的最大长度。
4. 参考代码

def get_str_len(s):
    tmp = ''
    r = [] 

    for i in range(len(s)):
        if s[i] not in tmp:
            tmp += s[i]
        else:
            r.append(tmp)
            n = tmp.index(s[i])
            tmp = tmp[n+1:] + s[i]

    r.append(tmp)
    return max(len(x) for x in r)

s = 'dvdf'
print(get_str_len(s))
3

方法二

1. 方法二与方法一的思路相同，区别是不再产生中间结果list，而是每次遍历时，返回最大的中间字符串长度；
2. 类似这样的，不需要将所有符合条件的数据生成中间结果后，再进行筛选判断，而是在遍历的同时，返回符合条件的数据，该方法更简洁优雅，效率也OK。
3. 参考代码

def get_str_len(s):
    tmp = ''
    r = 0 

    for v in s:
        if v not in tmp:
            tmp += v
        else:
            n = tmp.index(v)
            tmp = tmp[n+1:] + v
        r = max(len(tmp), r)
    return r 

s = 'dvdf'
print(get_str_len(s))
3

方法三

1. 该方法抽象出需求(无重复最长子串)的规律，通过简单遍历即可实现，但是理解起来有难度，更抽象，效率并卵有提升多少，感兴趣的话，可以了解一下思路；
2. 遍历字符串
   基于字符(key)和字符在字符串中的位置(value)构建字典d，存在重复字符时覆盖原有元素，值变更为新的字符位置；
   构建2个变量n/m：
   1）未出现重复字符前，n为0、m为d中元素个数；
   2）出现重复字符时：n为当前重复字符在字符串中上一次出现的位置，或者字符串中该重复字符之前其它重复字符在字符串中上一次出现的位置，取最大位置；m为当前字符在字符串中出现的位置，减去重复字符的最大位置(n)，即为最长的不重复子串。
3. 参考代码

def get_str_len(s):
    d = {}
    n, m = 0, 0

    for i in range(len(s)):
        if s[i] in d:
            n = max(d[s[i]], n)
            
        m = max(m, i + 1 - n)
        d[s[i]] = i + 1
    return m

s = 'dvdf'
print(get_str_len(s))
3