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:
longestNoDupeLength('abccc')
# 3
longestNoDupeLength('axbx')
# 3
longestNoDupeLength('deriveit')
# 5

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:

Longest No-Dupe Substring - image

You eventually get to a duplicate letter, like this:

Longest No-Dupe Substring - image

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.

Longest No-Dupe Substring - image

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:

i = 0 # left index
window = set()

for j in range(len(s)): # right index

    while s[j] in window:
        # shrink window
        window.remove(s[i])
        i += 1
    
    # grow window
    window.add(s[j])

Here's how you code this up:


def longestNoDupeLength(s):

    i = 0 # left index
    window = set()
    maxlen = 0

    for j in range(len(s)): # next elt

        while s[j] in window:
            # shrink window
            window.remove(s[i])
            i += 1
        # grow window
        window.add(s[j])

        maxlen = max(maxlen, len(window))
    
    return maxlen
        

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!