Longest substring without repeated characters

You're twenty minutes into a Bloomberg phone screen when the interviewer says, "Given a string, find the length of the longest substring that contains no repeated characters." You've seen hash maps, you've done two-pointer problems, but this one asks you to combine both ideas into something tighter: a sliding window. It's one of the most common medium-difficulty string problems at companies like Amazon, Microsoft, and Meta, and the difference between a clean solution and a messy one usually comes down to how well you manage the window boundaries.

TL;DR

Use a sliding window with a hash map that stores each character's most recent index. Advance the right pointer through the string one character at a time. When you encounter a character that already exists inside the current window, jump the left pointer past its previous occurrence. Track the maximum window size as you go. One pass, O(n) time, O(n) space.

Why This Problem Matters

The sliding window technique is a building block for dozens of string and array problems. Once you understand how to expand and contract a window while maintaining a validity condition, you can apply the same pattern to "minimum window substring," "longest substring with at most K distinct characters," and many others. This particular problem is the cleanest introduction to the pattern because the validity rule is simple: no duplicate characters inside the window.

Understanding the Problem

Given: A string of alphanumeric characters Find: The length of the longest substring with all unique characters Constraints: String length up to 1000, linear time target

Here are a few examples from the problem:

maxSubstringLength("BCEFGHBCFG") returns 6, because the longest substrings without repeated characters are "CEFGHB" and "EFGHBC", both having length 6.

maxSubstringLength("FFFFF") returns 1, because the only non-repeating substring is a single character "F".

maxSubstringLength("AAABBBABCDE") returns 5, because "ABCDE" at the end is the longest unique-character run.

Let's visualize the input string "BCEFGHBCFG" so we can trace through it:

Edge Cases

1. Empty string: Return 0 (no characters, no substrings)
2. All identical characters: Return 1 (the window never grows beyond a single character)
3. All unique characters: Return the string length (the window spans the entire input)
4. Duplicate outside the window: The last_seen_index >= start check prevents a false contraction

Solution Approach

The brute-force approach would check every possible substring and verify it has no duplicates. That's O(n^3) with nested loops and a uniqueness check. We can do much better with a single pass.

The idea is to maintain a window [start, i] over the string where every character inside the window is unique. Two things can happen as we advance i:

1. The character at i is new to the window. The window grows by one. Update maxLength if this is the largest window we've seen.
2. The character at i already exists in the window. We need to shrink the window from the left until the duplicate is removed.

A hash map that stores each character's most recent index lets us handle case 2 in O(1). Instead of shrinking one character at a time, we can jump start directly past the previous occurrence of the duplicate character.

The Critical Check: charIndexMap.get(c) >= start

This condition is what separates a correct solution from a buggy one. When we see a character that exists in the map, we only move start forward if the character's recorded index is inside the current window (at or after start). If the recorded index is before start, that occurrence is already outside the window and can be safely ignored.

Walkthrough

Let's trace through "BCEFGHBCFG" step by step.

Phase 1: Window Expansion (i=0 through i=5)

Characters B, C, E, F, G, H are all encountered for the first time. The window grows from length 1 to length 6 without any contractions.

At this point, the map contains {B:0, C:1, E:2, F:3, G:4, H:5} and maxLength = 6.

Phase 2: First Contraction at i=6

We encounter B again. The map says B was last seen at index 0, which is >= start (0). So start jumps to 0 + 1 = 1.

The window is now [1..6] = "CEFGHB", still length 6. We update B's index in the map to 6.

Phase 3: Second Contraction at i=7

C appears again. The map says C was last at index 1, which is >= start (1). So start jumps to 1 + 1 = 2.

The window is now [2..7] = "EFGHBC", still length 6. C's index is updated to 7.

Phase 4: Final Contractions (i=8 and i=9)

F at index 8 duplicates F at index 3 (which is >= start of 2), so start moves to 4. Then G at index 9 duplicates G at index 4 (which is >= start of 4), so start moves to 5. The window shrinks but maxLength holds steady at 6.

The final answer is 6.

Edge Case: All Duplicates

For input "FFFFF", every step finds a duplicate and start advances by one. The window never exceeds length 1:

Implementation

Prefer a different language? Jump to solutions in other languages.

Here's the Java solution with the sliding window approach:

import java.util.HashMap;
import java.util.Map;

public class Solution {
  public int maxSubstringLength(String input) {
    // Map each character to its most recent index
    Map<Character, Integer> charIndexMap = new HashMap<>();

    // start = left edge of window, maxLength = best result so far
    int start = 0, maxLength = 0;

    for (int i = 0; i < input.length(); i++) {
      char c = input.charAt(i);

      // If c is in the map AND its last index is inside the current window,
      // jump start past the previous occurrence
      if (charIndexMap.containsKey(c) && charIndexMap.get(c) >= start)
        start = charIndexMap.get(c) + 1;

      // Update maxLength with the current window size
      maxLength = Math.max(maxLength, i - start + 1);

      // Record (or overwrite) c's index
      charIndexMap.put(c, i);
    }

    return maxLength;
  }
}

Each step in this loop does constant work: one map lookup, one conditional update of start, one Math.max comparison, and one map write. The loop runs n times, giving us O(n) total.

Why i - start + 1?

Both i and start are zero-indexed. If start = 2 and i = 7, the window covers indices 2, 3, 4, 5, 6, 7, which is 6 characters. The formula 7 - 2 + 1 = 6 accounts for both endpoints being inclusive.

Complexity Analysis

Time Complexity: O(n)

The loop iterates once through every character. Inside the loop, HashMap.containsKey, HashMap.get, and HashMap.put are all O(1) amortized. The start pointer only moves forward, never backward, so total work across all iterations is bounded by n.

Space Complexity: O(n)

The hash map stores at most one entry per unique character. In the worst case (all unique characters), that's n entries. If the input alphabet is bounded (say, 128 ASCII characters), you could argue O(1) space, but in general it's O(n).

Alternative: Fixed-Size Array

If the problem guarantees ASCII input, you can replace the hash map with an int[128] array initialized to -1. This gives the same time complexity with lower constant overhead. In an interview, mention this optimization after presenting the hash map solution.

Common Pitfalls

1. Forgetting the >= start check: Without this guard, seeing a character that was recorded long before the current window would incorrectly move start backward. For example, in "abba", after processing the second b, start is at index 2. When you hit the second a, its recorded index is 0. Without the check, you'd set start = 1, which moves it backward and breaks the algorithm.

2. Using a set instead of a map: A HashSet can detect duplicates, but when one is found, you need to shrink the window one position at a time until the duplicate is removed. The map approach avoids this inner loop by jumping start directly.

3. Off-by-one in window length: The window [start, i] is inclusive on both ends, so its size is i - start + 1, not i - start.

4. Not updating the map after moving start: Even when start moves forward, you still need to record (or overwrite) the current character's index. The map stores the most recent index of each character, regardless of window boundaries.

Interview Tips

When presenting this solution:

1. Start by stating the brute-force complexity (O(n^3) or O(n^2) with a set). This frames the optimization.
2. Explain the sliding window concept before writing code. Draw the window on the whiteboard and show expansion vs. contraction.
3. Emphasize the >= start guard. Interviewers specifically look for whether you handle the "duplicate outside the window" case.
4. Mention the array optimization as a follow-up if time permits. It shows awareness of constant-factor improvements.
5. Test with "abba". This small input exercises the tricky case where a previously-seen character is outside the current window.

Key Takeaways

• The sliding window pattern maintains a valid range [start, i] and expands or contracts it in one pass, avoiding the nested loops of brute force.
• Storing each character's most recent index in a hash map lets you jump start past duplicates in O(1) instead of shrinking the window incrementally.
• The charIndexMap.get(c) >= start check is the core correctness condition. It prevents start from moving backward when a duplicate lies outside the current window.
• One pointer (i) always advances, and the other (start) only moves forward. This guarantees O(n) time.
• Trace your solution on "abba" during interviews. It's the smallest input that catches the most common bug in this problem.

Related Problems

Once you're comfortable with this sliding window approach, these related problems build on the same pattern:

• Longest substring with at most K distinct characters (add a frequency counter)
• Minimum window substring (shrink from the left when all target characters are covered)
• Longest repeating character replacement (track the most frequent character in the window)

Consistent practice with sliding window problems is one of the fastest ways to level up your string algorithm skills. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for interviews at companies like Amazon, Bloomberg, and Microsoft. Whether you're targeting your first offer or your next promotion, building fluency with patterns like sliding window will serve you well.

Solutions in Other Languages

Python

class Solution:
    def max_substring_length(self, input_str: str) -> int:
        char_index_map = {}
        start, max_length = 0, 0

        for i in range(len(input_str)):
            c = input_str[i]
            if c in char_index_map and char_index_map[c] >= start:
                start = char_index_map[c] + 1
            max_length = max(max_length, i - start + 1)
            char_index_map[c] = i

        return max_length

Python's dictionary provides O(1) average-case lookups, so the logic is identical to Java. The in operator checks membership, and direct key assignment overwrites previous values.

JavaScript

class Solution {
  maxSubstringLength(input) {
    const charIndexMap = new Map();
    let start = 0, maxLength = 0;

    for (let i = 0; i < input.length; i++) {
      const c = input.charAt(i);
      if (charIndexMap.has(c) && charIndexMap.get(c) >= start)
        start = charIndexMap.get(c) + 1;
      maxLength = Math.max(maxLength, i - start + 1);
      charIndexMap.set(c, i);
    }

    return maxLength;
  }
}

Using Map instead of a plain object is important here because Map.has() and Map.get() have guaranteed O(1) performance and avoid prototype chain issues.

TypeScript

class Solution {
  maxSubstringLength(input: string): number {
    const charIndexMap = new Map<string, number>();
    let start = 0, maxLength = 0;

    for (let i = 0; i < input.length; i++) {
      const c = input.charAt(i);
      if (charIndexMap.has(c) && charIndexMap.get(c)! >= start)
        start = charIndexMap.get(c)! + 1;
      maxLength = Math.max(maxLength, i - start + 1);
      charIndexMap.set(c, i);
    }

    return maxLength;
  }
}

The TypeScript version is identical to JavaScript with added type annotations. The non-null assertion ! after charIndexMap.get(c) is safe because the preceding has() check guarantees the key exists.

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>

class Solution {
public:
  int maxSubstringLength(std::string input) {
    std::unordered_map<char, int> charIndexMap;
    int start = 0, maxLength = 0;

    for (int i = 0; i < input.size(); i++) {
      char c = input[i];
      if (charIndexMap.find(c) != charIndexMap.end() && charIndexMap[c] >= start)
        start = charIndexMap[c] + 1;
      maxLength = std::max(maxLength, i - start + 1);
      charIndexMap[c] = i;
    }

    return maxLength;
  }
};

std::unordered_map provides amortized O(1) lookups. The find() != end() check avoids accidentally inserting a default value, which operator[] would do if the key is missing.

Go

package solution

type Solution struct{}

func (s *Solution) MaxSubstringLength(input string) int {
	charIndexMap := make(map[rune]int)
	start, maxLength := 0, 0

	for i, c := range []rune(input) {
		if idx, ok := charIndexMap[c]; ok && idx >= start {
			start = idx + 1
		}
		if currLen := i - start + 1; currLen > maxLength {
			maxLength = currLen
		}
		charIndexMap[c] = i
	}

	return maxLength
}

Go's range over a []rune slice iterates by sequential index and rune value, so i is always the logical character position. The two-value map lookup (idx, ok) is idiomatic Go for checking key existence.

Scala

import scala.collection.mutable

class Solution {
  def maxSubstringLength(input: String): Int = {
    val charIndexMap = mutable.Map[Char, Int]()
    var start = 0
    var maxLength = 0

    for (i <- 0 until input.length) {
      val c = input(i)
      if (charIndexMap.contains(c) && charIndexMap(c) >= start)
        start = charIndexMap(c) + 1
      maxLength = Math.max(maxLength, i - start + 1)
      charIndexMap.put(c, i)
    }

    maxLength
  }
}

The mutable Map is necessary here since we update character indices throughout the loop. Scala's 0 until input.length produces a half-open range matching the standard loop pattern.

Swift

import Foundation

class Solution {
    func maxSubstringLength(_ input: String) -> Int {
        var charIndexMap: [Character: Int] = [:]
        var start = 0
        var maxLength = 0

        for (i, c) in input.enumerated() {
            if let lastIndex = charIndexMap[c], lastIndex >= start {
                start = lastIndex + 1
            }
            maxLength = max(maxLength, i - start + 1)
            charIndexMap[c] = i
        }

        return maxLength
    }
}

Swift's optional binding with if let cleanly handles the "key exists" check and value extraction in a single expression.

Kotlin

class Solution {
    fun maxSubstringLength(input: String): Int {
        val charIndexMap = mutableMapOf<Char, Int>()
        var start = 0
        var maxLength = 0

        for (i in input.indices) {
            val c = input[i]
            if (charIndexMap.containsKey(c) && charIndexMap[c]!! >= start) {
                start = charIndexMap[c]!! + 1
            }
            maxLength = maxOf(maxLength, i - start + 1)
            charIndexMap[c] = i
        }

        return maxLength
    }
}

Kotlin's maxOf function is a convenient alternative to Math.max. The !! operator asserts non-null, which is safe after the containsKey check.

Ruby

class Solution
  def max_substring_length(input)
    char_index_map = {}
    start = 0
    max_length = 0

    input.each_char.with_index do |c, i|
      start = char_index_map[c] + 1 if char_index_map.key?(c) && char_index_map[c] >= start
      max_length = [max_length, i - start + 1].max
      char_index_map[c] = i
    end

    max_length
  end
end

Ruby's each_char.with_index provides both the character and its position. The postfix if keeps the duplicate check concise.

Rust

use std::collections::HashMap;

pub struct Solution;

impl Solution {
    pub fn max_substring_length(&self, input: String) -> i32 {
        let mut char_index_map: HashMap<char, usize> = HashMap::new();
        let mut start = 0;
        let mut max_length = 0;

        for (i, c) in input.chars().enumerate() {
            if let Some(&idx) = char_index_map.get(&c) {
                if idx >= start {
                    start = idx + 1;
                }
            }
            max_length = max_length.max(i - start + 1);
            char_index_map.insert(c, i);
        }

        max_length as i32
    }
}

Rust's ownership model requires &c for the map lookup (borrowing the key). The if let Some pattern is idiomatic for optional value extraction.

C#

using System;
using System.Collections.Generic;

public class Solution {
    public int MaxSubstringLength(string input) {
        var charIndexMap = new Dictionary<char, int>();
        int start = 0, maxLength = 0;

        for (int i = 0; i < input.Length; i++) {
            char c = input[i];
            if (charIndexMap.ContainsKey(c) && charIndexMap[c] >= start)
                start = charIndexMap[c] + 1;
            maxLength = Math.Max(maxLength, i - start + 1);
            charIndexMap[c] = i;
        }

        return maxLength;
    }
}

C#'s Dictionary<char, int> provides the same hash map semantics. The indexer charIndexMap[c] = i both inserts new entries and overwrites existing ones.

Dart

import 'dart:math';

class Solution {
  int maxSubstringLength(String input) {
    Map<String, int> charIndexMap = {};
    int start = 0, maxLength = 0;

    for (int i = 0; i < input.length; i++) {
      String c = input[i];
      if (charIndexMap.containsKey(c) && charIndexMap[c]! >= start) {
        start = charIndexMap[c]! + 1;
      }
      maxLength = max(maxLength, i - start + 1);
      charIndexMap[c] = i;
    }

    return maxLength;
  }
}

Dart uses String for individual characters accessed via bracket notation. The ! operator handles null safety after the containsKey check.

PHP

class Solution {
    public function maxSubstringLength(string $input): int {
        $charIndexMap = [];
        $start = 0;
        $maxLength = 0;

        for ($i = 0; $i < strlen($input); $i++) {
            $c = $input[$i];
            if (isset($charIndexMap[$c]) && $charIndexMap[$c] >= $start) {
                $start = $charIndexMap[$c] + 1;
            }
            $maxLength = max($maxLength, $i - $start + 1);
            $charIndexMap[$c] = $i;
        }

        return $maxLength;
    }
}

PHP's associative arrays act as hash maps. isset() checks for key existence without triggering undefined-index warnings.