Longest Substring Without Repeating Characters Solution for Capgemini

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

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. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""

Output: 0

Explanation: Empty string has length 0.

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.

This ensures that our current window always contains unique characters.

Approach

Approach 1: Sliding Window with Hash Table (Optimal)

1. Use a hash table to store the last index of each character

2. Use two pointers: start and end of current window

3. When we encounter a character that's already in our window:

• Move start pointer to max(start, lastIndex[char] + 1)

4. Update the hash table with current character's index

5. Update maxLength if current window is longer

Approach 2: Sliding Window with Array

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

2. Same logic as Approach 1 but with array indexing

Approach 3: Brute Force

1. Check all possible substrings

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

3. Keep track of maximum length found

Dry Run

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

Sliding Window Approach:

• start = 0, end = 0, char = 'a'
• lastIndex['a'] = 0, maxLength = 1
• start = 0, end = 1, char = 'b'
• lastIndex['b'] = 1, maxLength = 2
• start = 0, end = 2, char = 'c'
• lastIndex['c'] = 2, maxLength = 3
• start = 0, end = 3, char = 'a'
• 'a' already exists at index 0
• start = max(0, 0 + 1) = 1
• lastIndex['a'] = 3, maxLength = 3
• start = 1, end = 4, char = 'b'
• 'b' already exists at index 1
• start = max(1, 1 + 1) = 2
• lastIndex['b'] = 4, maxLength = 3

Continue until end reaches end of string

Key Insights

1. Sliding Window: Maintain a window of unique characters

2. Hash Table: Track last occurrence of each character

3. Window Adjustment: Move start when duplicate is found

4. Contiguous Substring: Must be consecutive characters

Edge Cases

1. Empty string: Return 0

2. Single character: Return 1

3. All same characters: Return 1

4. No duplicates: Return string length

5. Unicode characters: Consider extended ASCII or Unicode

More Capgemini coding questions