Reader Solutions Reviewed: Sliding Window

Challenge: Longest Substring Without Repeating Characters

Problem recap

Interview question
Given a string s, return the length of the longest substring without repeating characters.

Examples:

• s = "abcabcbb" → 3 (answer is "abc")

• s = "bbbbb" → 1 (answer is "b")

• s = "pwwkew" → 3 (answer is "wke")

Constraints typically look like:

• 1 <= s.length <= 5 * 10^4

• Characters are usually standard ASCII; LeetCode’s version allows spaces, punctuation, etc.

---

Baseline idea: sliding window over a string

Naive thinking says: enumerate all substrings and check them one by one. That’s O(n^2) substrings and O(n) to check each, which is dead on arrival.

Instead, this problem is a textbook variable-size sliding window:

• Maintain a window [left, right] that always has no duplicates.

• Expand right one character at a time.

• If the new character makes the window invalid (duplicate), move left forward until the window is valid again.

• Track the best window length seen so far.

All of the implementations below share this same mental model; they only differ in how they detect and fix duplicates (array vs. hash map vs. set).

---

Approach 1: Hash map frequency (clean, general-purpose)

This is the version I’d expect a strong candidate to reach first in an interview: use a hash map from character → count to track what’s inside the window.

Python (hash map)

def length_of_longest_substring(s: str) -> int:
    freq = {}          # char -> count in current window
    left = 0
    best = 0

    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        # If ch is now duplicated, shrink from the left
        while freq[ch] > 1:
            left_ch = s[left]
            freq[left_ch] -= 1
            if freq[left_ch] == 0:
                del freq[left_ch]
            left += 1

        best = max(best, right - left + 1)

    return best

Java (hash map)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        freq.put(c, freq.getOrDefault(c, 0) + 1);

        while (freq.get(c) > 1) {
            char leftChar = s.charAt(left);
            freq.put(leftChar, freq.get(leftChar) - 1);
            if (freq.get(leftChar) == 0) {
                freq.remove(leftChar);
            }
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

C# (dictionary)

public int LengthOfLongestSubstring(string s) {
    var freq = new Dictionary<char, int>();
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.Length; right++) {
        char c = s[right];
        freq[c] = freq.GetValueOrDefault(c) + 1;

        while (freq[c] > 1) {
            char leftChar = s[left];
            freq[leftChar]--;
            if (freq[leftChar] == 0) {
                freq.Remove(leftChar);
            }
            left++;
        }

        best = Math.Max(best, right - left + 1);
    }

    return best;
}

Complexity

• Time: O(n), each character enters and leaves the window at most once.

• Space: O(k) where k is the number of distinct characters in the window, k≤128 for ASCII.

When this shines

• You want a generic sliding window template that adapts to “at most K occurrences”, “at most K distinct characters”, etc.

• You’re not sure about the character set (could be Unicode, emojis, etc.).

---

Approach 2: Hash set + left pointer (simpler state)

If all you care about is “no duplicates at all”, you don’t actually need counts—just membership. A hash set stores the characters in the current window.

Python (set)

def length_of_longest_substring_set(s: str) -> int:
    seen = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # If ch is already in the window, move left until it's gone
        while ch in seen:
            seen.remove(s[left])
            left += 1

        seen.add(ch)
        best = max(best, right - left + 1)

    return best

Java (HashSet)

public int lengthOfLongestSubstringSet(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        while (seen.contains(c)) {
            seen.remove(s.charAt(left));
            left++;
        }

        seen.add(c);
        best = Math.max(best, right - left + 1);
    }

    return best;
}

C# (HashSet)

public int LengthOfLongestSubstringSet(string s) {
    var seen = new HashSet<char>();
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.Length; right++) {
        char c = s[right];

        while (seen.Contains(c)) {
            seen.Remove(s[left]);
            left++;
        }

        seen.Add(c);
        best = Math.Max(best, right - left + 1);
    }

    return best;
}

Complexity

• Time: O(n) average with set operations expected O(1).

• Space: O(k) distinct characters, like the map approach.

When this shines

• You want the simplest readable solution for this specific problem.

• You don’t need frequency counts or more complex constraints.

---

Approach 3: Character index array (true O(1) space for ASCII)

In many LeetCode-style constraints, the input is restricted to ASCII. When that’s true, you can trade generality for a flat array indexed by character code, which removes hashing overhead and pins space to a constant.

Two common patterns:

1. Last-seen index: lastIndex[c] = last index where c appeared, or -1 if never.

2. Frequency array: Like the map-based sliding window, but with an array of length 128.

I like the last-seen-index version because it eliminates the inner while loop and keeps the window valid by jumping left forward in one step.

Python (last-seen index, ASCII)

def length_of_longest_substring_ascii(s: str) -> int:
    # 128 for standard ASCII; use 256 or 256k if needed
    last_index = [-1] * 128

    left = 0
    best = 0

    for right, ch in enumerate(s):
        code = ord(ch)

        # If we've seen this char inside the current window, move left
        if last_index[code] >= left:
            left = last_index[code] + 1

        last_index[code] = right
        best = max(best, right - left + 1)

    return best

Java (last-seen index, ASCII)

public int lengthOfLongestSubstringAscii(String s) {
    int[] lastIndex = new int[128];
    Arrays.fill(lastIndex, -1);

    int left = 0;
    int best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        int code = (int) c;

        if (lastIndex[code] >= left) {
            left = lastIndex[code] + 1;
        }

        lastIndex[code] = right;
        best = Math.max(best, right - left + 1);
    }

    return best;
}

C# (last-seen index, ASCII)

public int LengthOfLongestSubstringAscii(string s) {
    int[] lastIndex = new int[128];
    Array.Fill(lastIndex, -1);

    int left = 0;
    int best = 0;

    for (int right = 0; right < s.Length; right++) {
        char c = s[right];
        int code = (int)c;

        if (lastIndex[code] >= left) {
            left = lastIndex[code] + 1;
        }

        lastIndex[code] = right;
        best = Math.Max(best, right - left + 1);
    }

    return best;
}

Complexity

• Time: O(n).

• Space:

  • Array length is fixed (e.g., 128), so strictly O(1) with respect to input size.

When this shines

• You’re in a tight performance setting (competitive programming, very large number of test cases, strict limits).

• The interviewer has explicitly restricted the alphabet to ASCII or to a small known set.

---

Comparison: map vs. set vs. array

Here’s how these approaches stack up from an interviewer’s point of view.

Here k is the number of distinct characters, which is bounded by 128 for ASCII but may be larger in Unicode scenarios.

---

When does “O(1) space” actually matter here?

On paper, all three are “O(n) time, O(1)/O(k) space”, and it’s tempting to optimize preemptively. In actual interviews, I’d bucket it like this:takeuforward+3

1. Most interviews

   • The map or set solution is completely fine.

   • The real evaluation is about:

     • Recognizing the sliding window pattern.

     • Managing indices and invariants cleanly.

     • Explaining why the algorithm is O(n) (each char enters/leaves the window at most once).

2. Performance-obsessed interviewers / follow-up questions

   • They may ask: “Can you do it in O(1) space?”

   • That’s your cue to say:

     • “If we can assume the input is ASCII, we can replace the map with a fixed-size array indexed by character code, which makes the additional space independent of n.”

   • Dropping that shows you can connect constraints to implementation choices.

3. When not to over-optimize

   • If your first attempt with the array is buggy or hard to explain, it’s worse than a clean map-based solution.

   • Most production environments don’t care about the tiny constant-factor improvement here unless you’re processing giant logs in a tight loop.

A good rule you can even say out loud: “I’ll start with the hash map version for clarity, and if we need to squeeze constants or space, we can switch to a fixed-size array given ASCII constraints.”

Want to see how interviewers really grade this problem?

The paid section breaks down why two almost-identical solutions get very different outcomes in real interviews: what strong candidates say about their window invariant, complexity, and follow-ups that upgrades this into a genuine positive signal.

➡️ Unlock the interviewer’s rubric for this problem

Paid-only add-on: How interviewers really grade this problem