Longest stretch of a log with no letter seen twice

Sliding window Mid-level Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Spot the bug

This version gives 3 for 'abba' instead of 2. Which line is wrong?

  1. def stretch(s: str) -> int:
  2. last: dict[str, int] = {}
  3. left = best = 0
  4. for right, ch in enumerate(s):
  5. if ch in last:
  6. left = last[ch] + 1
  7. last[ch] = right
  8. best = max(best, right - left + 1)
  9. return best
  10. print(stretch("abba"))

Choose an answer, then open Show answer below to check it.

Show answer
  • Answer: line 5 if ch in last:

Line 5 accepts any earlier sighting, even one before the window. At the final 'a', left jumps back from 2 to 1, so the window wrongly includes two b's. The check must be last.get(ch, -1) >= left.

30-second answer

Slide a window and remember the last index of each character. When the new character was last seen inside the window, jump the left edge just past that index. Every character is processed once, so it is O(n) time and O(k) space for k distinct characters.

Practise saying it · 45 s. No recording, just a timer

Explain the last-seen map window.

Say your answer out loud, then check which of these points you covered:

  • Map of last index
  • Jump left past the repeat
  • Ignore stale sightings

Deep dive

Jumping left straight to last[ch] + 1 avoids a shrink loop; the check >= left ignores stale positions from before the window.

A set-based version shrinks one character at a time; it is also O(n) amortised.

For a fixed alphabet (say 128 ASCII codes) the map can be a list, and space is O(1).

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def longest_fresh_stretch(log: str) -> int:
    last: dict[str, int] = {}
    left = best = 0
    for right, ch in enumerate(log):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun longestFreshStretch(log: String): Int {
    val last = HashMap<Char, Int>()
    var left = 0
    var best = 0
    for ((right, ch) in log.withIndex()) {
        val seen = last[ch]
        if (seen != null && seen >= left) left = seen + 1
        last[ch] = right
        best = maxOf(best, right - left + 1)
    }
    return best
}

Common mistakes

  • Moving left backwards when the earlier sighting is before the window.
  • Resetting the whole window on a repeat instead of moving just past the earlier copy.

Senior take & follow-ups

Mention both the jump version and the shrink-with-a-set version; pick one and say why.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if at most two copies of each letter are allowed?

    Show hint

    Count letters in the window and shrink while any count passes 2.

  2. How would you return the stretch itself?

    Show hint

    Store the start whenever best improves.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.