Iteration

Longest No-Dupe Substring

Longest Sliding Window

Given string s of lowercase letters, find the longest substring that has no repeated characters.

A "substring" is a consecutive sequence in the original string.

Example:

s = "abcaaa"=> returns 3\notag \begin{align*} &\texttt{s = "abcaaa"}\\ &\texttt{=> returns 3} \end{align*}

Explanation: The longest string without a repeated character is "abc".

First Few Test Cases:

To solve this problem, you can use a sliding window approach. You want to grow keep adding a new element to the window, like this:

You eventually get to a duplicate letter, like this:

You have to remove one of the "b"'s from this window, because it's a duplicate. The trick is to delete letters from the beginning of the the window until you remove the very first duplicate.

You won't miss out on any valid solutions when you do this, because you've already considered the largest possible substring that involves the first "b" in the previous window. This means you've considered every possible solution to the problem.

To solve the problem, you can keep growing the window from the right, and shrinking it from the left. Here's the logic for this:

Here's how you code this up:

Time Complexity O(n)O(n). We do a single for-loop.

Space Complexity O(1)O(1). We have to store 26 letters, which is O(26) = O(1).

Mark as Completed:
Submits:
longestNoDupeLength
Test your code to get an output here!
longestNoDupeLength(
)
Test your code to get an output here!