Python solution with detailed explanation


  • 0
    G

    Solution

    Longest Substring Without Repeating Characters https://leetcode.com/problems/longest-substring-without-repeating-characters/

    Two Pointer Technique

    • Two pointers start and end
    • Use a hash table to store indices of the letters. When we encounter a duplicate character, test if its index in cache is >= start. If yes, update max_so_far and move start pointer to the next index of the duplicate character.
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            cache, start, end, max_so_far = {}, 0, 0, 0
            while end < len(s):
                c = s[end]
                if c in cache and start <= cache[c]:
                    max_so_far = max(max_so_far, end-start)
                    start = cache[s[end]] + 1
                cache[c], end = end, end + 1
            return max(max_so_far, end-start)
    

    Two pointer using a set

    • Maintain start and end as two pointers and initialize to zero.
    • Move end to right and keep building a valid solution and keep adding every character to a set.
    • When you hit a character which is already in set, compute max_so_far. Then start moving start pointer to right and keep removing characters till you hit the duplicate character. Then just move the start pointer to right by 1.
    • Note we do not need so_far variable to maintain the current run. end-start will help us track that.
    • Pay special attention towards maintaining invariants after adjusting the start pointer. Make sure how the end pointer will move and what all elements are in the set.
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            start, end = 0, 0
            max_so_far, temp = -1, set([])
            while end < len(s):
                if s[end] not in temp:
                    temp.add(s[end])
                else:
                    max_so_far = max(max_so_far, end - start)
                    while s[start] != s[end]:
                        temp.remove(s[start])
                        start += 1
                    start += 1
                end += 1
            return max(max_so_far, end - start)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.