Leetcode # 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters

Solution: Sliding Window

Time Complexity: O(len(s))
Space Complexity: O(26) = O(1) (26 lowercase letters)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    appeared_c = collections.Counter()
    ans = left = 0
    for right in range(len(s)):
      # do logic here to add arr[right] to curr
      appeared_c[s[right]] += 1

      while appeared_c[s[right]] > 1:
        # remove arr[left] from curr
        appeared_c[s[left]] -= 1
        left += 1
    
      # update ans
      ans = max(ans, right - left + 1)
    
    return ans

Optimized Solution

Time Complexity: O(len(s))
Space Complexity: O(26) = O(1) (26 lowercase letters)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    ans, left, indeces = 0, 0, {}    
    for right, c in enumerate(s):
      # c has appeared in s[left:right + 1]
      if c in indeces and left <= indeces[c]: 
        left = indeces[c] + 1
      ans = max(ans, right - left + 1)
      indeces[c] = right
    return ans

Test 例

s = “abba”

當 right == 3
indeces[“a”] = 1 < left == 2

Last Updated on 2023/09/06 by A1go