PPractick

The problem

A password-strength meter rewards long stretches of distinct characters. For a given string, it needs the length of the longest contiguous substring with no repeated character. Checking every substring is O(n²) or worse. A sliding window does it in one pass: extend the right end one character at a time, and when that character already appears inside the window, jump the left end to just past its previous occurrence. Remembering the last index of each character makes the jump O(1).

Example: "abcabcbb" → 3 ("abc").

Function signature

int lengthOfLongestSubstring(const string& s);

Test cases

Input	Output	Explanation
"abcabcbb"	3	"abc"
"bbbbb"	1
"pwwkew"	3	"wke"; "pwke" is not contiguous
""	0
"abba"	2	The left end must never move backwards
"dvdf"	3	"vdf"

(Confirm: substring means contiguous; characters are arbitrary bytes, including spaces and symbols.)

How interviewers phrase it

• "Given a string s, find the length of the longest substring without repeating characters" (LeetCode 3).

Clarifying questions to ask

1. Substring (contiguous) or subsequence? (Substring.)
2. What character set? (ASCII: a 256-entry table works; for Unicode, use a hash map.)
3. Length only, or the substring itself? (Length; tracking the start is a small extension.)

Follow-ups to expect

1. "Why check last[c] >= left?"
2. "Set-based variant?"
3. "Why is it O(n)?"
4. "How do you return the substring?"
5. "Complexity?"

Related questions

• Count Number of Substrings Easy
• Longest Repeating Character Replacement Hard
• Number of Substrings Containing All Three Characters Hard
• Longest Substring With At Most K Distinct Characters Hard
• Minimum Window Substring Hard
• Minimum Window Subsequence Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in