3. Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: s

s is a string and also an list of characters
rst ← 0
n ← length(s)
for i ← 0 to n - 1
  dic ← empty set
  for length ← 1 to n - i
    ss ← s[i:i + length]
    for ch in ss[length - 1:]  # start from current position
      if ch is in dic
        go to next i
      else
        add ch to dic
        rst ← max(rst, length(ss))
return rst

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    self.rst = 0
    self.n = len(s)
    for i in range(self.n):
      self.checkSubstring(s, i)
    return self.rst

  def checkSubstring(self, s, i):
    dic = set()
    for length in range(1, self.n - i + 1):
      ss = s[i:i + length]
      for ch in ss[length - 1:]:
        if ch in dic:
          return
        else:
          dic.add(ch)
          self.rst = max(self.rst, len(ss))