Crack the Backend

Problem Statement

Given a string s, find the length of the longest substring that contains no repeating characters.

A substring is a contiguous sequence of characters within s.
"No repeating characters" means every character in the substring appears exactly once.
The string can contain letters, digits, symbols, and spaces; character set is typically ASCII or Unicode.
If s is empty, return 0.

Key Observations

Any valid substring is a contiguous window [left, right] in which each character has frequency at most 1. So we can maintain a sliding window and a frequency (or count) map for characters inside the window.
When we extend with right, we add s[right]. If that character was already in the window, the window becomes invalid; we must shrink from left until that duplicate is removed (i.e., until the count of s[right] is 1).
The window is always valid after shrinking, so at each right we can record right - left + 1 as a candidate for the maximum length.
Each character is added at most once and removed at most once, so the total cost is O(n).

Approach

High-level: Maintain a window [left, right] and a count map for characters in the window. Expand with right; whenever the new character repeats, shrink left until the window has no duplicate. Track the maximum window size.

Steps:

Use two pointers left, right and a Map<Character, Integer> (or int array for fixed alphabet) for counts in the current window.
For each right: increment count[s[right]]. While count[s[right]] > 1, decrement count[s[left]] and left++.
Update best = max(best, right - left + 1).
Return best.

Implementation

Java

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

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count.merge(c, 1, Integer::sum);

        while (count.get(c) > 1) {
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }

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

    return best;
}

Test Cases

Example 1

Input

s = "abcabcbb"

Expected

3

Explanation

The longest substring without repeating characters is "abc" (length 3).

Complexity Analysis

Time: O(n). Each character is added to the window at most once and removed at most once.
Space: O(min(n, |alphabet|)) for the frequency map.

Follow-ups

How would you return the substring itself (not just the length)? Track left and right when you update the maximum length, then return s.substring(left, right+1).
What if the string is very long and you only need the length? The same algorithm applies; no need to store the substring.