0003. Longest Substring Without Repeating Characters

Medium | String + Two Pointer | 36 ms (99.77%), 13.7 MB (73.48%)

❓ Problem Statement

Source: LeetCode - Longest Substring Without Repeating Characters GitHub: Solution / Performance

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

✍🏻 Constraints & Example

💡 Ideas

Instead of checking each possible substring in the input string:

We could use two pointers to form a sliding window to get the longest substring.

Regarding the repeating characters, we could use the hash table (dict or set in Python) to record each character in the current sliding window.

🤖 Python3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # (base case)
        if not s: return 0
        
        # ==================================================
        #  Hash Table + Sliding Window (Two Pointer)       =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        table = set()
        slowP, fastP = 0, 0
        ans = float('-inf')
        
        while fastP < len(s):
            if s[fastP] not in table:
                table.add(s[fastP])
                fastP += 1
                ans = max(ans, fastP - slowP)
                
            else:
                table.remove(s[slowP])
                slowP += 1
                
        return ans

🤖 Java