Longest Substring Without Repeating Characters

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The longest substring without repeating characters is "abc".

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The only substring without repeats is "b".

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: "wke" is the longest valid window. "pwke" is not a substring because it is not contiguous.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols, and spaces.

Difficulty: Medium LC: 3 Round: OA

---

Pattern Recognition

• What is the input structure? A flat string of arbitrary characters.
• What are we optimizing? The length of the longest contiguous window containing no duplicate characters.
• What pattern does this fit? Sliding Window with a hash map. The window expands when the new character is unseen and contracts when a duplicate is found.
• Why does this pattern fit? Once you add a duplicate, the new longest valid window must start strictly after the previous occurrence of that duplicate. This lets you move left forward without ever moving it backward — the hallmark of the sliding window pattern.

If you tried brute force (check every substring), you would be enumerating O(n^2) windows and validating each in O(n), giving O(n^3). The sliding window collapses this because left is monotonic.

---

Approach

Brute Force — Check Every Substring

Enumerate every pair (i, j), check whether s[i..j] has duplicates using a set, track the max length.

best = 0
for i in 0..n-1:
    seen = set()
    for j in i..n-1:
        if s[j] in seen: break
        seen.add(s[j])
        best = max(best, j - i + 1)

Time: O(n^2) average, O(n^3) if you rebuild the set inside the loop naively. Space: O(min(n, charset)). Why insufficient: For n = 50,000, O(n^2) is 2.5 billion ops — TLE on any reasonable limit.

Optimal — Sliding Window with Last-Seen Index

Key Insight: When you encounter a duplicate, the left boundary of any valid window must jump to lastSeen[char] + 1. You never need to move left backward, so every index is touched at most twice (once by right, once by left).

Step-by-step:

1. Maintain left = 0 and a lastSeen map from character to its most recent index.
2. Scan right from 0 to n-1.
3. If s[right] was seen before and its last index is >= left, jump left to lastSeen[s[right]] + 1.
4. Record lastSeen[s[right]] = right.
5. Track best = max(best, right - left + 1).

The prev >= left check matters: if the last occurrence is already behind the current window, it is irrelevant — do not shrink.

Time: O(n) — each index visited by right exactly once, left moves only forward. Space: O(min(n, charset size)) — bounded by the number of distinct characters.

---

Walkthrough

Trace on s = "pwwkew":

right	char	lastSeen before	left before	action	left after	best
0	p	{}	0	new	0	1
1	w		0	new	0	2
2	w		0	dup at 1 >= 0 → left = 2	2	2
3	k		2	new (p at 0 < 2 is irrelevant even if p showed up)	2	2
4	e		2	new	2	3
5	w		2	dup at 2 >= 2 → left = 3	3	3

Answer: 3 (window "kew" at indices 3..5, or equivalently "wke" at 2..4).

Note how at right = 5, the prev >= left check is important. If the last 'w' had been at an index before left, you would not shrink.

---

Implementation

TypeScript

function lengthOfLongestSubstring(s: string): number {
    const lastSeen = new Map<string, number>();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        const ch = s[right];
        const prev = lastSeen.get(ch);
        // Only jump left if the previous occurrence is inside the window.
        if (prev !== undefined && prev >= left) {
            left = prev + 1;
        }
        lastSeen.set(ch, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

C++

#include <string>
#include <unordered_map>
#include <algorithm>

int lengthOfLongestSubstring(std::string s) {
    std::unordered_map<char, int> lastSeen;
    int left = 0;
    int best = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char ch = s[right];
        auto it = lastSeen.find(ch);
        // Only jump left if the previous occurrence is inside the window.
        if (it != lastSeen.end() && it->second >= left) {
            left = it->second + 1;
        }
        lastSeen[ch] = right;
        best = std::max(best, right - left + 1);
    }
    return best;
}

Watch out:

1. Forgetting the prev >= left check. If the duplicate is behind the current window, it is already invalid. Shrinking anyway produces wrong answers on strings like "abba".
2. Using Set.has + Set.delete in a while loop. Works, but every duplicate causes a linear shrink instead of an O(1) jump. Map-of-indices is strictly better.
3. Off-by-one on window length. Length is right - left + 1, not right - left.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2) to O(n^3)	O(min(n, charset))
Optimal Sliding Window	O(n)	O(min(n, charset))

Bottleneck: You must read every character at least once — O(n) is optimal. Space is bounded by the charset (128 for ASCII, 26 for lowercase-only).

---

Edge Cases

1. Empty string — return 0. Loop does not execute, best stays 0.
2. Single character — return 1. One iteration, window is [0, 0].
3. All identical characters ("aaaa") — answer is 1. The jump-to-prev+1 rule ensures the window collapses to one cell each time.
4. No duplicates ("abcdef") — answer is n. left never moves.
5. Duplicate outside current window ("abba") — at right = 3 (char 'a'), prev = 0 but left = 2, so you do not shrink. Without the prev >= left guard you would reset left to 1, corrupting the window.
6. Unicode / multi-byte characters — s[i] in JavaScript returns code units, not code points. Clarify with the interviewer whether surrogate pairs matter.

---

Related Problems

• LC 76 — Minimum Window Substring — Sliding window but the goal flips: find the smallest window containing all chars of another string. Uses a frequency map instead of last-seen indices.
• LC 159 / 340 — Longest Substring with At Most K Distinct Characters — Same window shape, different shrink condition (distinct count > k).
• LC 424 — Longest Repeating Character Replacement — Sliding window where you track the max-frequency character and allow up to k replacements.
• LC 1695 — Maximum Erasure Value — Same structure with numeric array and sum instead of length.

---

OA Strategy Notes

This is reported as the most common Salesforce OA problem. Two problems in 75 minutes means you have roughly 30 focused minutes per solve with 10 minutes of buffer. If this is your problem 1, aim to have it submitted in 15-20 minutes so you bank time for the harder second question. The pattern is standard — the risk is only the prev >= left guard, which is the single most-missed detail.

---

What is Expected at Each Level

Junior: Recognize sliding window. May first write the Set.delete shrinking variant and get to correct with O(n^2) shrinks. With a hint about "jump instead of shrink," arrive at the map-of-indices solution.

Mid-level: Go straight to the map-of-indices solution. Correctly handle the prev >= left guard without prompting. Discuss ASCII vs Unicode briefly.

Senior: Derive the O(n) complexity precisely (each index touched at most twice). Offer the fixed-size array variant for ASCII (256-entry array for constant-factor speedup). Anticipate the follow-up of returning the substring itself and modify the code in one line.