Longest Substring Without Repeating Characters Solution for Amazon

Company: Amazon · Difficulty: Medium · Topics: String, Hash Table, Sliding Window, Two Pointers

Problem Statement

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

A substring is a contiguous sequence of characters within a string.

Examples

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.

Example 4:

Input: s = ""

Output: 0

Explanation: Empty string has length 0.

Example 5:

Input: s = "abcdef"

Output: 6

Explanation: The answer is "abcdef", with the length of 6.

Intuition

The key insight is to use a sliding window approach with two pointers. We keep track of characters we've seen in a hash table and expand/shrink the window accordingly.

Approach

Approach 1: Sliding Window with Hash Table (Optimal)

1. Use two pointers (left and right) to maintain a sliding window

2. Use a hash table to track characters in the current window

3. Expand right pointer and add characters to hash table

4. If duplicate found, shrink left pointer until no duplicates

5. Keep track of maximum window size

Approach 2: Sliding Window with Array

1. Use an array of size 128 (ASCII characters) instead of hash table

2. Same logic as hash table approach but with array indexing

3. More memory efficient for ASCII strings

Approach 3: Brute Force

1. Check all possible substrings

2. For each substring, check if it has repeating characters

3. Keep track of maximum length found

Dry Run

Let's trace through Example 1: s = "abcabcbb"

Sliding Window Approach:

left=0, right=0: "a" → maxLen=1, seen={'a'}
left=0, right=1: "ab" → maxLen=2, seen={'a','b'}
left=0, right=2: "abc" → maxLen=3, seen={'a','b','c'}
left=0, right=3: "abca" → duplicate 'a', left=1: "bca" → maxLen=3, seen={'b','c','a'}
left=1, right=4: "bcab" → duplicate 'b', left=2: "cab" → maxLen=3, seen={'c','a','b'}
left=2, right=5: "cabc" → duplicate 'c', left=3: "abc" → maxLen=3, seen={'a','b','c'}
left=3, right=6: "abcb" → duplicate 'b', left=4: "cb" → maxLen=3, seen={'c','b'}
left=4, right=7: "cbb" → duplicate 'b', left=5: "b" → maxLen=3, seen={'b'}

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Sliding Window with Hash Table (Optimal)

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(min(m,n)) - Hash table size

Solution 2: Sliding Window with Array

Time Complexity: O(n) - We traverse the string once

Space Complexity: O(1) - Fixed size array

Solution 3: Brute Force

Time Complexity: O(n³) - Check all substrings

Space Complexity: O(min(m,n)) - Hash table for each substring