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

Constraints:

• 0 <= s.length <= 5 * 10^4

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

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Input: s = ""
Output: 0

💡 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

class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
     
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> hashTable = new HashMap<>();
        int ans = 0, slowP = 0, fastP = 0;
        
        int length = s.length();
        if( length == 0 ){ return 0; }
        
        while( fastP < length ){
            char curChar = s.charAt( fastP );
            
            if( !hashTable.containsKey( curChar ) ){
                hashTable.put( curChar, fastP );
                fastP++;
                ans = Math.max( ans, fastP-slowP );
                
            } else {
                curChar = s.charAt( slowP );
                hashTable.remove( curChar );
                slowP++;
            }
        }
        
        return ans;
    }
}