How can I search for longest substring in a more efficient way?-CodePudding

I'm trying to search for the longest substring in a string, in linear time. How can I do this without using the max function?

This is the question:

Given a string, find the length of the longest substring without repeating characters. Can you find a solution in linear time?

And this is my solution:

class Solution:
  def lengthOfLongestSubstring(self, sentence):

     evid = []
     word = ''

     for i in sentence:
      if i not in word:
        word  = i
      else:
        evid.append(word)
        word = ''
        word  = i

     return len(max(evid, key=len))

print(Solution().lengthOfLongestSubstring('abrkaabcdefghijjxxx'))

Thank you!

CodePudding user response：

You should not operate on strings when it comes to membership testing (O(N)). A truly linear solution would use a set and two pointers:

class Solution:
    def lengthOfLongestSubstring(self, sentence):
        crnt = set()
        m = lo = hi = 0
        
        while hi < len(s):
            if (c := s[hi]) in crnt:  # membership check is O(1)
                # move lo past the most recent occurrence of c
                while (d := s[lo]) != c:
                    # removing all characters along the way
                    crnt.remove(d)
                    lo  = 1
                lo  = 1
            else:
                crnt.add(c)
                if len(crnt) > m:
                    m = len(crnt)
            hi  = 1
        
        return m

As every index/char is added to and removed from the crnt set at most once with both operations and the contains-check all being O(1), this approach is linear.

CodePudding user response：

Same idea to use sliding window and avoid using max as OP requested. Try this to see if that's helpful?

 def lengthOfLongestSubstring(self, s: str) -> int:
           
     maxSubLen = 0
     start = 0
     seen = {}
     for i in range(len(s)):
         c = s[i]
         if c in seen and start <= seen[c]:
            start = seen[c]   1
         else:
             if maxSubLen > (i-start  1):
                maxSubLen = maxSubLen
             else:
                 maxSubLen = i - start   1
                 #maxSubLen = max(maxSubLen, i - start   1) # no max! 
         seen[c] = i
                
    return maxSubLen