Longest Substring Without Repeating Characters Solution for Google

Company: Google · Difficulty: Medium · Topics: String, Sliding Window, Hash Table

Problem Statement

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

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.

Intuition

The key insight is to use a sliding window approach with a hash table to track the last occurrence of each character. When we encounter a repeating character, we move the start of the window to the position after the last occurrence of that character.

Approach

1. Use two pointers (start and end) to represent the current window

2. Use a hash table to store the last occurrence of each character

3. For each character:

• If it's already in the window, move start to after its last occurrence
• Update the last occurrence of current character
• Update the maximum length

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: Sliding Window with Hash Table

Time Complexity: O(n) - Single pass through the string

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

More Google coding questions