3. Longest Substring Without Rep

题目描述

Given a string, find the length of the longest substring without repeating characters.

Solution:

思路

从左往右loop一遍，通过update开始与结尾的index，找出最长且符合要求的区间。

Detail

1. 用set S记录current区间中已有元素，用int count记录目前为止最长的长度，开头i，结尾j
2. i 和 j都从0开始，对于s中的每个新的char (即 j 所指元素):
   a. 若不在S中，说明 current区间 可以扩展，j往后移动并且把该char加入S，同时看是否需要更新count，此时 i 不变
   b. 若在S中, 说明已经达到 从 i 算起 符合要求的最长区间， 此时将s[i] 从S中移除，并将 i 往后移动一位，此时 j 不变，且count无需更新
3. 当 j 到达s尾时结束
4. 返回count

Complexity

• Time: O(n)
• Space: O(n)

    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        count = 0;
        S = set()
        i = 0
        j = 0
        while (j < n):
            if (s[j] not in S):
                S.add(s[j])
                j += 1
                count = max(count, j-i)
            else:
                S.remove(s[i])
                i += 1
        return count

后续

Solve it without using "set S"