Longest Streak of Distinct Keys

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Longest Streak of Distinct Keys

A logger records a stream of keystrokes as a string s. You want the length of the longest run of consecutive keystrokes with no repeated character.

Return the length of the longest substring of s without repeating characters.

def length_of_longest_substring(s):
    pass

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Strings, Sliding Window, Hash Map

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: Does the streak have to be a contiguous run of keystrokes, or can we skip characters?
- A: It must be contiguous. We are looking for the longest substring without repeating characters, not a subsequence.
Q: What should we return if every keystroke is the same character?
- A: The longest streak of distinct keys is a single character, so we return 1.
Q: What should we return if the string is empty?
- A: There are no keystrokes, so the longest streak has length 0.

HAPPY CASE
Input: s = "abcabcbb"
Output: 3
Explanation: The longest streak without a repeat is "abc", which has length 3.

Input: s = "pwwkew"
Output: 3
Explanation: The longest streak without a repeat is "wke", which has length 3. Note that "pwke" is a subsequence, not a substring.

EDGE CASE
Input: s = "bbbbb"
Output: 1
Explanation: Every character repeats, so the longest streak of distinct keys is a single "b".

Input: s = ""
Output: 0
Explanation: With no keystrokes recorded, the longest streak has length 0.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Substring/Contiguous Window Problems, we can consider the following approaches:

Sliding Window: Maintain a window [start, end] over the string that always contains distinct characters, expanding the right edge and shrinking the left edge when a repeat appears.
Hash Map: Store the most recent index of each character so that when a repeat is found, the left edge of the window can jump directly past the previous occurrence instead of shrinking one step at a time.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Slide a window across the string that always contains distinct characters. Track the most recent index of each character in a hash map. When the current character has already been seen inside the window, move the window's start to just past that previous occurrence. The answer is the largest window size observed.

1) Initialize an empty hash map `last_seen` mapping each character to its most recent index.
2) Initialize `start = 0` (left edge of the window) and `longest = 0`.
3) For each index `end` and character `char` in the string:
   a) If `char` is in `last_seen` and `last_seen[char] >= start`, the repeat is inside the
      current window, so move `start` to `last_seen[char] + 1`.
   b) Update `last_seen[char] = end`.
   c) Update `longest = max(longest, end - start + 1)`.
4) Return `longest`.

⚠️ Common Mistakes

Confusing substring with subsequence and skipping over repeated characters instead of restarting the window.
Moving start backwards when a repeat is found before the current window (always take max or check last_seen[char] >= start).
Forgetting to update the character's most recent index on every iteration, not just when a repeat is found.
Returning the final window size instead of the maximum window size seen at any point.

4: I-mplement

Implement the code to solve the algorithm.

def length_of_longest_substring(s):
    last_seen = {}  # Maps each character to its most recent index
    start = 0       # Left edge of the current window of distinct characters
    longest = 0

    for end, char in enumerate(s):
        # If this character was seen inside the current window, slide the
        # left edge just past its previous occurrence
        if char in last_seen and last_seen[char] >= start:
            start = last_seen[char] + 1

        # Record the most recent index of this character
        last_seen[char] = end

        # The window [start, end] contains only distinct characters
        longest = max(longest, end - start + 1)

    return longest

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input: s = "abcabcbb"
- The window grows to "abc" (longest = 3).
- At the second a (index 3), start jumps to 1; the window slides as "bca", "cab", "abc", each of size 3.
- At the second-to-last b (index 6), start jumps to 5; at the final b (index 7), start jumps to 7.
- Output: 3
Input: s = "bbbbb"
- Every character after the first is a repeat inside the window, so start chases end and the window never exceeds size 1.
- Output: 1
Input: s = "pwwkew"
- The window grows to "pw" (longest = 2).
- At the second w (index 2), start jumps to 2; the window then grows to "wke" (longest = 3).
- At the final w (index 5), start jumps to 3, giving "kew", also size 3.
- Output: 3

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the string s and K is the size of the character set (e.g. 26 for lowercase letters, 128 for ASCII).

Time Complexity: O(N) because each character is processed exactly once; the hash-map lookup lets start jump directly past a repeat rather than shrinking one step at a time.
Space Complexity: O(min(N, K)) for the hash map, which stores at most one entry per distinct character in the string.

Uh oh!

Longest Streak of Distinct Keys