CODEWITHSUNDEEP
pythonperformance
NotAName
NotAName

Reputation: 4347

How to optimise run time and memory usage of code for finding the longest substring?

I solved the question on LeetCode where you need to find the longest substring without repeating characters, but currently my code is using too much memory (~37Mb) and runs quite slowly compared to other submissions. My solution is this:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        strings = [0,]
        for a in range(len(s)):
            sub = s[a]
            strings.append(len(sub))
            for char in s[a+1:]:
                if char not in sub:
                    sub += char
                else:                    
                    break                     
                strings.append(len(sub))
        return max(strings)

How can I improve the performance of the code? Is there a specific algorithm I should look into? Thanks!

Upvotes: 0

Views: 175

Answers (1)

Issei Kumagai
Issei Kumagai

Reputation: 685

You have to use an algorithm called 'Sliding Window' (which is a bit like a 2-pointer algorithm). In the below solution, the 'start' variable is the pointer used.

Also, please understand the usage of hash-maps/sets/dictionaries. I have used a dictionary since you are able to lookup/search a key in O(1) Time Complexity. You are also able to insert a key in O(1) Time Complexity.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        dic, ans, start = {}, 0, 0
        for i, v in enumerate(s):
            if v not in dic or dic[v] < start:
                ans = max(ans, i - start + 1)
            else:
                start = dic[v] + 1
            dic[v] = i
        return ans

This kind of questions come up quite a bit in tech interviews, so make sure you fully understand the solution I have placed above.

Upvotes: 2

Related Questions