AI Hints
Home›DSA in Python Tutorial›Windows and Prefixes
DSA in Python · Lesson 26 of 132

Practice: Longest Substring

No repeated characters.

⏱ 2 min read▶ Video at 29:56🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Find the length of the longest part of a string with no repeated characters. In ABCABCBB, the answer is three, ABC. Pause, and think about a window that grows and shrinks.

Practice: Longest Substring
From the video: Practice: Longest Substring
  • Longest stretch with no repeats
  • abcabcbb → 3
  • Grow and shrink a window

A growing window

Start marks the left edge of the window. A dictionary remembers where we last saw each character. When we meet a character that's already inside the window, we move start just past its last position. Then we record the new position, and the best length so far. Run it. Three, one, and three.

longest.pypython
def longest_unique(s):
    last = {}
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

for s in ["abcabcbb", "bbbbb", "pwwkew"]:
    print(s, "->", longest_unique(s))
Output
abcabcbb -> 3
bbbbb -> 1
pwwkew -> 3

How to spot a window problem

Look for words like longest, shortest, or best, together with substring, or subarray, or in a row. Those are strong hints for a sliding window. The data is in one line, and you care about a continuous stretch of it.

keyvalue
Longest / shortesta strong hint
Substring / subarraycontinuous stretch
In a rowconsecutive items
Track the edgesstart and end

Summary

A growing window, plus a dictionary of last positions, finds the longest stretch without repeats in O of N. Next, prefix sums. Precompute once, then answer instantly.

Key takeaways
  • Move start past the repeat
  • Remember last positions
  • O(n)
Next up: Prefix Sums — answer range questions instantly