3.Longest_Substring_Without_Repeating_Characters_(Medium).md

3. Longest Substring Without Repeating Characters (Medium)

Date and Time: Jun 4, 2024, 12:10 PM (EST)

Link: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Question:

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

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Edge Case 1:

Input: s = " "

Output: 1

Edge Case 2:

Input: s = "abba"

Output: 2

Walk-through:

Maintain a sliding window with non-repeated characters. When there is no repeated character exists, we repeatedly update res = max(res, r - l + 1). When we have a char that exists in hashmap{}, we start shrinking the sliding window by removing the left-most character.

Sliding Window:

May 26, 2026, [Time Taken 25m]

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Maintain sliding window with dict{}
        # Otherwise, we comapre the current length with res
        # TC: O(n), SC: O(n)
        dict = {}
        res = 0
        l = 0
        for r in range(len(s)):
            # Identify if s[r] is char
            # if s[r].isalnum():
            dict[s[r]] = dict.get(s[r], 0) + 1
            # If s[r] is repeated, remove all previous char in dict
            while dict[s[r]] > 1:
                dict[s[l]] -= 1
                l += 1
            else:
                # Otherwise compare with current res
                res = max(res, r - l + 1)
        return res

Time Complexity: $O(n)$, n is length of s.
Space Complexity: $O(n)$

Sliding Window:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Q: Find the longest substring without duplicate characters
        # S: Sliding window with l, r ptr and a hashmap{char: cnt}
        # Expand r ptr if no duplicate characters
        # If duplicate char exists, move l ptr
        # TC: O(n), n=len(s), SC: O(n)

        hashmap = collections.defaultdict(int)
        ans = 0
        l = 0
        for r in range(len(s)):
            hashmap[s[r]] += 1
            # If duplicate char exists, shrink the sliding window by updating l ptr and hashmap
            while hashmap[s[r]] > 1:
                hashmap[s[l]] -= 1
                l += 1
            # Update ans
            ans = max(ans, r - l + 1)
        return ans

Time Complexity: $O(n)$, n is length of s.
Space Complexity: $O(n)$

Java

class Solution {
    /* 
    Maintain sliding window by l, r ptr and hashmap{char: cnt}
    Expand r ptr everytime, add s[r] into hashmap, and check if duplicate char exists
    If so, shrink the sliding window by removing s[l] and increment l ptr
    TC :O(n), n = len(s), SC: O(n)
    */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> hashmap = new HashMap<>();
        int l = 0;
        int ans = 0;
        for (int r = 0; r < s.length(); r++) {
            hashmap.put(s.charAt(r), hashmap.getOrDefault(s.charAt(r), 0) + 1);
            // Check if duplicate char exists
            while (hashmap.get(s.charAt(r)) > 1) {
                hashmap.put(s.charAt(l), hashmap.get(s.charAt(l)) - 1);
                l++;
            }
            // Update ans
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}