Python Leetcode 3: Time limit exceeded

Question

I am solving LeetCode problem https://leetcode.com/problems/longest-substring-without-repeating-characters/:

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

Constraints:

0 <= s.length <= 5 * 104

s consists of English letters, digits, symbols and spaces.

If used this sliding window algorithm:

def lengthOfLongestSubstring(str):
    # define base case
    if (len(str) < 2): return len(str)

    # define pointers and frequency counter
    left = 0
    right = 0
    freqCounter = {} # used to store the character count
    maxLen = 0

    while (right < len(str)):
        # adds the character count into the frequency counter dictionary
        if (str[right] not in freqCounter):
            freqCounter[str[right]] = 1
        else:
            freqCounter[str[right]] += 1
            # print (freqCounter)
        # runs the while loop if we have a key-value with value greater than 1. 
        # this means that there are repeated characters in the substring. 
        # we want to move the left pointer by 1 until that value decreases to 1 again. E.g., {'a':2,'b':1,'c':1} to {'a':1,'b':1,'c':1}
        while (len(freqCounter) != right-left+1):
        # while (freqCounter[str[right]] > 1): ## Time Limit Exceeded Error
            print(len(freqCounter), freqCounter)
            freqCounter[str[left]] -= 1
            # remove the key-value if value is 0
            if (freqCounter[str[left]] == 0):
                del freqCounter[str[left]]
            left += 1
        
        maxLen = max(maxLen, right-left+1)
        # print(freqCounter, maxLen)
        right += 1
    
    return maxLen

print(lengthOfLongestSubstring("abcabcbb")) # 3 'abc'

I got the error "Time Limit Exceeded" when I submitted with this while loop:

while (freqCounter[str[right]] > 1):

instead of

while (len(freqCounter) != right-left+1):

I thought the first is accessing an element in a dictionary, which has a time complexity of O(1). Not sure why this would be significantly slower than the second version. This seems to mean my approach is not optimal in either case. I thought sliding window would be the most efficient algorithm; did I implement it wrong?

Comments are not for extended discussion; this conversation has been moved to chat. — sideshowbarker
– sideshowbarker, Commented Nov 27, 2022 at 9:58

trincot · Accepted Answer · 2022-11-26 17:43:46Z

Your algorithm running time is close to the timeout limit for some tests -- I even got the time-out with the version len(freqCounter). The difference between the two conditions you have tried cannot be that much different, so I would look into more drastic ways to improve the efficiency of the algorithm:

Instead of counting the frequency of letters, you could store the index of where you last found the character. This allows you to update left in one go, avoiding a second loop where you had to decrease frequencies at each unit step.
Performing a del is really not necessary.
You can also use some more pythonic looping, like with enumerate

Here is the update of your code applying those ideas (the first one is the most important one):

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        lastpos = {}
        left = 0
        maxLen = 0

        for right, ch in enumerate(s):
            if lastpos.setdefault(ch, -1) >= left:
                left = lastpos[ch] + 1
            else:
                maxLen = max(maxLen, right - left + 1)
            lastpos[ch] = right
        return maxLen

Another boost can be achieved when you work with ASCII codes instead of characters, as then you can use a list instead of a dictionary. As the code challenge guarantees the characters are from a small set of basic characters, we don't need to take other character codes into consideration:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        lastpos = [-1] * 128
        left = 0
        maxLen = 0

        for right, asc in enumerate(map(ord, s)):
            if lastpos[asc] >= left:
                left = lastpos[asc] + 1
            else:
                maxLen = max(maxLen, right - left + 1)
            lastpos[asc] = right
        return maxLen

When submitting this, it scored very well in terms of running time.

Collectives™ on Stack Overflow

Python Leetcode 3: Time limit exceeded

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related