3. Longest Substring Without Repeating Characters - Detailed Explanation

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. The goal is to find a substring where no character appears more than once, and then return its length.

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

Approach

The most efficient approach to solve this problem is by using the Sliding Window technique along with a hash map or a set. This method allows us to maintain a window of characters that are unique and adjust the window dynamically as we iterate over the string.

Steps of the Sliding Window Technique

1. Initialize two pointers:

   • Use two pointers, left and right, both starting at the beginning of the string.

2. Expand the window:

   • Move the right pointer to the right, adding characters to the current window.
   • Use a hash map (or set) to keep track of the characters and their indices in the current window.

3. Detect and handle duplicates:

   • If a character is encountered that is already in the current window (i.e., it exists in the hash map with an index that is within the current window), adjust the left pointer:
     • Move left to one position right of the previous occurrence of that character. This ensures that the window contains only unique characters.

4. Update the maximum length:

   • At each step, calculate the current window's length (right - left + 1) and update the maximum length if the current window is larger.

5. Continue until the end:

   • Repeat the process until the right pointer has traversed the entire string.

This approach ensures that each character is processed at most twice (once by right and once by left), leading to an efficient solution.

Step-by-Step Walkthrough

Consider the string "pwwkew":

• Initialization:
  left = 0, right = 0, max_length = 0, and an empty hash map.

• Iteration 1:

  • right = 0, character = 'p'.
  • 'p' is not in the map; add {'p': 0}.
  • Current window = "p", length = 1 → update max_length to 1.

• Iteration 2:

  • right = 1, character = 'w'.
  • 'w' is not in the map; add {'p': 0, 'w': 1}.
  • Current window = "pw", length = 2 → update max_length to 2.

• Iteration 3:

  • right = 2, character = 'w'.
  • 'w' is in the map with index 1, which is within the current window.
  • Move left to index 2 (one position right of index 1).
  • Update 'w' in the map to the current index: {'p': 0, 'w': 2}.
  • Current window = "w", length = 1 → max_length remains 2.

• Iteration 4:

  • right = 3, character = 'k'.
  • 'k' is not in the map; add {'p': 0, 'w': 2, 'k': 3}.
  • Current window = "wk", length = 2 → max_length remains 2.

• Iteration 5:

  • right = 4, character = 'e'.
  • 'e' is not in the map; add {'p': 0, 'w': 2, 'k': 3, 'e': 4}.
  • Current window = "wke", length = 3 → update max_length to 3.

• Iteration 6:

  • right = 5, character = 'w'.
  • 'w' is in the map with index 2, which is within the current window.
  • Move left to index 3 (one position right of index 2).
  • Update 'w' in the map to index 5.
  • Current window = "kew", length = 3 → max_length remains 3.

The iteration ends with a maximum length of 3.