LeetCode 3. Longest Substring Without Repeating Characters

September 02, 2022

This looks like something we can solve in linear time with a sliding window.

The sliding window could be a hash map of characters that we've seen mapped to the index of that character in our input. We track the current non-repeating substring with start and end indices. At any point, we know the length of our current non-repeating substring. If we run into a repeat, we need to remove:

the previous occurence of this character
all characters before that in the current non-repeating substring

We add each character to the hash map once and we remove each character at most once.

The runtime of this algorithm is $O(n)$ and the space complexity is $O(n)$ .

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_leetcode_examples(self):
        self.assertEqual(self.s.lengthOfLongestSubstring("abcabcbb"), 3)
        self.assertEqual(self.s.lengthOfLongestSubstring("bbbbb"), 1)
        self.assertEqual(self.s.lengthOfLongestSubstring("pwwkew"), 3)
        self.assertEqual(self.s.lengthOfLongestSubstring("bpfbhmipx"), 7)

    def test_symbols(self):
        self.assertEqual(self.s.lengthOfLongestSubstring(" .&* "), 4)

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        res = 0
        w = {}
        start = 0
        for i in range(len(s)):
            c = s[i]
            if c in w:
                res = max(res, i-start)
                for j in range(start, w[c]):
                    del w[s[j]]
                start = w[c]+1
                del w[c]
            w[c] = i 
        return max(res, len(s)-start)


if __name__=="__main__":
    unittest.main()