Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

描述

给定一个字符串, 输出最长的无重复字符子串的长度

示例:
输入: abcabc
输出: 3

分析

最简单的思路是使用两个指针, 固定一个, 另一个向后遍历, 使用 set 记录遇到的字符, 遇到重复时记录长度, 复杂度为\(O(n^2)\)

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_cnt = 0
        m = set()
        cnt = 0
        for i in range(0, len(s)):
            m.add(s[i])
            cnt = 1
            for j in range(i + 1, len(s)):
                if s[j] not in m:
                    m.add(s[j])
                    cnt += 1
                    continue
                break
            max_cnt = cnt if cnt > max_cnt else max_cnt
            m = set()
        return cnt if cnt > max_cnt else max_cnt

功能上是可以的, 但是提交时因为时间过长超过限制不能通过

来分析一下, “abcdebhijk”这个字符串, 在第一次遇到重复的”b”字符时, 第一个”b”与第二个”b”之间的字符串是没有重复字符的, 所以在遍历时, 只需要向前移动第一个指针到第一个”b”字符之后, 同时, 记录的 cnt 相应减小, 减小值为第一个指针移动的距离即可, 第二个指针只需要向前遍历, 不需要回退, 这样, 整个查找复杂度就变为\(O(n)\)

答案

按照之前的分析, 一个复杂度为\(O(n)\)的答案为

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        slen = len(s)
        if slen == 0:
            return 0

        m = {s[0]:0}
        max_cnt = cnt = 1
        i = j = 0

        while j < slen - 1:
            j += 1

            if s[j] not in m:
                m[s[j]] = j
                cnt += 1
                continue

            max_cnt = cnt if cnt > max_cnt else max_cnt

            cnt = cnt - (m[s[j]] - i)

            for k in range(i, m[s[j]]):
                del(m[s[k]])

            i = m[s[j]] + 1
            m[s[j]] = j

        return cnt if cnt > max_cnt else max_cnt
打赏