Sliding-Window Techniques: Solving Array and String Problems with Window Invariants

Welcome back. In the previous lesson, a hash map remembered values from earlier array positions so you could find a pair in one pass. Today, the state has a different job: it describes a contiguous range that moves through an array or string.

We’ll solve an interview problem in Kotlin: find the length of the longest substring with no repeated characters. The aim is not just to produce working code, but to explain exactly what the window contains, when it is valid, and why a nested loop still takes linear time. Allow about 40–45 minutes, including the video and a short coding pass.

Recognize the kind of range you need

A substring consists of consecutive characters. In "abcdb", "cdb" is a substring; taking "a", then skipping to "c" is not. That requirement suggests maintaining a window bounded by two indices, left and right, rather than considering arbitrary combinations of positions.

There are two common window shapes. If a problem specifies “exactly $k$ consecutive elements,” the window has a fixed size: as one element enters, another leaves. If the size depends on a condition—such as “keep every character distinct”—the window is variable: right advances through the input, and left advances whenever necessary to restore the condition.

Read the short comparison below for the fixed-size case. Our implementation afterward will use the variable-size case.

For our substring problem, no size is given. The window should grow while its characters are unique and shrink when an incoming character would repeat one already inside it.

Define the invariant before moving the pointers

Here is the contract we will implement: given a Kotlin String, return the length of its longest contiguous substring containing no repeated Char values. An empty string returns 0. For example, "abba" returns 2, for "ab" or "ba".

Keep a HashSet<Char> alongside the two boundaries. After each iteration, the set must contain exactly the characters in the window s[left..right], and each of those characters must be unique. Before the next character is added, it is not yet part of that window. If it is already in the set, remove characters at left, advancing left each time, until adding it will be safe.

Greg Hogg’s “Longest Substring Without Repeating Characters” walks through this approach visually and then codes it in Python. Watch for the distinction between checking whether the incoming character would cause a duplicate and recording a window only after that issue is resolved. We’ll write the same idea in Kotlin.

The diagram gives another view of that movement. Its repeated "b" forces the left boundary past the earlier "b"; the window can then grow again.

Notice that moving left without updating the set would break the invariant. The set would still claim an excluded character belongs to the window, potentially making every later occurrence look like a duplicate.

Implement and trace the variable window

We can now translate the rule directly. The outer loop chooses each incoming character once. The inner loop removes as many characters from the left as needed before that character is added.

fun longestUniqueSubstringLength(s: String): Int {
    val windowChars = HashSet<Char>()
    var left = 0
    var longest = 0

    for (right in s.indices) {
        val incoming = s[right]

        while (incoming in windowChars) {
            windowChars.remove(s[left])
            left++
        }

        windowChars.add(incoming)
        longest = maxOf(longest, right - left + 1)
    }

    return longest
}

We update longest after the shrink phase and insertion, when the window is valid. Because both boundary indices are included, its length is $right-left+1$, not $right-left$.

Trace "abcdbfchx" against the code. The first four characters form "abcd". At the next "b", removing "a" is not enough: "b" is still in the set. Removing the earlier "b" moves left to the "c" and makes "cdb" valid.

The answer is 6. The window at the end supplies one longest substring, but the function stores only its length; it never needs to allocate substring copies.

For a brief coding pass, type the function into a Kotlin scratch file and run these calls. They cover an empty input, an all-duplicate input, a duplicate that needs several removals, and a window that grows again after shrinking:

fun main() {
    println(longestUniqueSubstringLength(""))           // 0
    println(longestUniqueSubstringLength("aaaa"))       // 1
    println(longestUniqueSubstringLength("abba"))       // 2
    println(longestUniqueSubstringLength("abcdbfchx"))  // 6
}

In "abba", processing the second "b" removes "a" and the earlier "b". The result remains 2, even though the current window has become shorter. That is why longest records the best valid window seen so far rather than simply returning the final window’s length.

Justify correctness and cost

A good interview explanation separates two claims.

First, the window is valid after every iteration. It starts empty. Assume the set exactly represents a unique window before considering s[right]. If the incoming character is absent, adding it preserves uniqueness. If it is present, each removal drops the actual leftmost window character from the set. Once the incoming character is absent, adding it again produces a set that exactly represents a unique s[left..right].

Second, this is the longest valid window ending at right. We move left only when required to exclude a repeated character. Starting any earlier would retain a duplicate. A start ruled out by an earlier duplicate cannot become valid merely by appending another character. Thus, at every right, the algorithm measures the longest valid substring ending there. Taking the maximum of those measurements finds the longest one anywhere in the string.

The nested while does not make the algorithm quadratic. right visits each of the $n$ positions once, and left only moves forward—at most $n$ times in total across all outer iterations. With expected constant-time hash-set operations, the time is $O(n)$ expected. The set stores at most one entry per character in the window, giving $O(\min (n,|\text{alphabet}|))$ additional space, commonly stated as $O(n)$ when the possible alphabet is not treated as a fixed constant.

One contract detail matters in Kotlin: String indexing uses UTF-16 Char values. The code therefore defines “character” as a Char, which is a reasonable explicit assumption for an interview prompt using a basic character set. If a product requirement means user-perceived Unicode characters instead, clarify that requirement before claiming this implementation handles it.

Key takeaways

A sliding window is useful when the answer concerns a contiguous range and you can update its state as boundaries move. For this problem, the invariant is precise: after each iteration, the set equals the contents of a duplicate-free window. Remove state when left moves, measure only valid windows, and justify linear time by counting total pointer movement—not by judging the loops’ nesting alone.

Next, we’ll turn to parameterized unit tests. The boundary cases you just ran are a starting point for testing a Kotlin function systematically, including its failure behavior where a contract permits failure.