9 · Strings, two pointers and sliding windows Code

Immutability, split/join, isalnum · opposing and fast/slow pointers · fixed and variable windows

Why it matters for NPE. String normalisation is half of every parsing task, and window problems are the common 'medium' asked after a warm-up.

Primer: one pass, two indices, a small amount of state

Every problem on this page is solved by walking the input once while keeping a few integers and maybe one dict. The brute force is always "try every pair" or "try every substring", O(n²) or worse. The improvement is always the same move: notice what a second index lets you skip. Two pointers skip pairs that cannot work. A sliding window skips recomputing a sum or a count that only changed at the edges. A prefix sum skips re-adding a range you already added. Interviewers grade the invariant you state as much as the code, because the invariant is what proves the skipping is safe.

The reported NPE question in this family is "is this string a palindrome, ignoring punctuation and case". It was asked more than once. It is easy, which is exactly why you must be fast, clean, and ready for "now do it without extra memory".

Watch

Strings: what costs what

A Python str is immutable. s[0] = 'x' raises TypeError. Every method that looks like it edits a string (lower, replace, strip, slicing) returns a new string and leaves the old one alone. Two consequences matter in an interview.

• Building a string with += in a loop is O(n²) in principle: each step copies everything so far. Collect pieces in a list and ''.join once, which is O(total length). CPython sometimes optimises the append in place, but you cannot rely on it and the interviewer knows that.
• Slicing copies. s[i:j] costs O(j - i). s[::-1] costs O(n). Comparing s[i:i+k] == p inside a loop over i makes the loop O(n·k). Use indices and counts instead of slices when the slice is inside the loop.

import string, re

s.lower(), s.upper(), s.casefold()      # casefold handles non-ASCII (ß → ss); lower is enough for the screen
c.isalnum(), c.isalpha(), c.isdigit(), c.isspace()   # per character; also work on whole strings
s.strip(), s.strip('.,;'), s.rstrip('\n')
s.startswith('ERROR'), s.count('a')
s.find('x')                               # -1 if absent; s.index('x') raises ValueError instead
s.replace(',', ' '), s.split(), s.split(',', 1), s.partition('=')
''.join(parts)                            # O(total length); the only right way to build a string in a loop
s[::-1]                                   # reversed copy, O(n)
ord('a'), chr(97)                         # letter → 0..25 index: ord(c) - ord('a')

# strip punctuation in one line (3-argument maketrans: the third argument is the delete set)
clean = s.translate(str.maketrans('', '', string.punctuation))

# keep only letters and digits, lowercased
clean = ''.join(c for c in s.lower() if c.isalnum())
clean = re.sub(r'[^a-z0-9]', '', s.lower())

# pull words out of free text (the word-frequency question)
words = s.split()                                   # whitespace only: "world!" keeps its "!"
words = re.findall(r"[a-z0-9']+", s.lower())        # tokens of letters/digits; punctuation becomes a boundary
words = re.split(r'[,;\s]+', s.strip())             # several delimiters at once

isdigit is true for some Unicode digits that int() rejects (superscripts). For "is this field an integer" prefer try: int(x) except ValueError, as in topic 5. Say that if asked.

Two pointers

Two indices into the same array or two arrays. The pattern is defined by where the pointers start, which one moves, and what stays true between moves. Each pointer moves at most n times, so the total is O(n) with O(1) extra space.

Opposing ends: Valid Palindrome, worked in full

The question as reported: "given a string, return whether it is a palindrome ignoring punctuation, spaces and case". Give the two-line version first because it is fast and correct, then the in-place version when asked about memory.

def is_palindrome(s):                     # O(n) time, O(n) extra space
    t = ''.join(c for c in s.lower() if c.isalnum())
    return t == t[::-1]

Follow-up: "without building a new string". Walk inward from both ends and skip non-alphanumerics as you go.

def is_palindrome(s):                     # O(n) time, O(1) extra space
    i, j = 0, len(s) - 1
    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1
        if s[i].lower() != s[j].lower():
            return False
        i += 1
        j -= 1
    return True

Invariant: every alphanumeric character outside [i, j] has already been matched with its mirror. Why the inner while loops need i < j: on ".," both pointers would otherwise run past each other and index out of range. Why lower() per character and not once up front: the whole point of this version is no copy. Edge cases to say: empty string and a string of only punctuation are palindromes (" " returns True on LeetCode). "0P" is not a palindrome; digits count. Each pointer moves at most n times in total across both the inner and outer loops, so it is O(n), not O(n²).

Clarifying questions worth 20 seconds: Unicode or ASCII? Are digits significant? Should an empty input be True? Asking them is graded.

Read/write pointer: Move Zeroes

In-place filtering that must keep the relative order of the kept items. One pointer reads every element; the other marks the next free slot in the finished prefix.

def move_zeroes(nums):
    w = 0                                  # next write slot
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

Invariant: nums[:w] holds every non-zero seen so far, in original order; nums[w:r] is all zeros. The swap moves a non-zero down into the finished prefix and a zero up into the gap. Because w <= r always, nothing unread is overwritten. O(n) time, O(1) space, stable. Remove Duplicates from Sorted Array and Remove Element are the same loop with a different if.

Merging from the back: Merge Sorted Array

nums1 has m sorted values followed by n empty slots; nums2 has n sorted values. Merge into nums1 in place. Merging from the front would overwrite values of nums1 you have not read yet. The free space is at the back, so fill from the back with the largest remaining value.

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:                                   # when nums2 is exhausted, nums1's remainder is already in place
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]; i -= 1
        else:
            nums1[k] = nums2[j]; j -= 1
        k -= 1

Invariant: nums1[k+1:] holds the largest m + n - 1 - k values of both arrays, sorted; every unplaced value is in nums1[:i+1] or nums2[:j+1]. Since k = i + j + 1, writing at k never touches an unread nums1[i] while j >= 0. O(m + n) time, O(1) space. The front-to-front version of this merge with a fresh output list is how you merge two sorted log files (lab 9); for k files use heapq.merge (topic 7).

Sliding windows

A window is a contiguous range [left, right] plus an aggregate that describes exactly that range: a sum, a count of zeros, a set of characters, a Counter. The window moves right one element at a time, and the aggregate is updated at the edges in O(1) instead of being recomputed in O(k). Three shapes.

The variable window only works when the condition is monotone: adding an element can only make a valid window invalid, never the reverse. "At most k zeros" and "no repeated characters" are monotone. "Sum equals k" with negative numbers is not, which is why Subarray Sum Equals K uses prefix sums below.

Fixed size: Maximum Average Subarray I

def find_max_average(nums, k):
    s = sum(nums[:k])                      # the first window, O(k)
    best = s
    for r in range(k, len(nums)):
        s += nums[r] - nums[r - k]         # slide: add the new right, drop the old left
        best = max(best, s)
    return best / k

Invariant: after the update, s is the sum of nums[r-k+1 .. r]. O(n) time, O(1) space. Compare max of sums, divide once at the end: fewer float operations and no rounding surprises. This loop is the template for "requests per 5-minute window" over a list of per-minute counts.

Variable size: Longest Substring Without Repeating Characters, worked in full

Version one uses a set and a shrink loop. It shows the shape; type this if you are unsure.

def length_of_longest_substring(s):
    seen = set()                           # characters in the current window
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:                  # WHILE, not if: may need to drop several characters
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1) # inclusive window length
    return best

Invariant: after the while, s[left:right+1] contains no repeated character and seen is exactly its character set. left only moves right, and each character is added and removed at most once, so the whole thing is O(n) even though there is a loop inside a loop. Space is O(min(n, alphabet)).

Version two jumps left straight past the duplicate using a last-seen index. This is the version to show when asked "can you avoid the inner loop".

def length_of_longest_substring(s):
    last = {}                              # ch → index of its most recent occurrence
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:   # a repeat INSIDE the current window
            left = last[ch] + 1               # jump past it
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Dry-run on "abba": at the second b (index 2), last['b'] = 1 >= left = 0, so left = 2. At the second a (index 3), last['a'] = 0, which is less than left = 2: a stale entry outside the window. Without the >= left check you would set left = 1, moving the window backwards and reporting 3 instead of 2. That check is the single most common bug in this problem. The answer is 2 ("ab" or "ba").

Variable size with a budget: Max Consecutive Ones III

Longest run of 1s if you may flip at most k zeros. Read it as "longest window containing at most k zeros". In NPE terms: longest healthy streak allowing k failed probes.

def longest_ones(nums, k):
    left = 0
    zeros = 0                              # zeros inside the window
    best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > k:                   # shrink until the budget holds again
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Invariant: after the while, the window has at most k zeros. Every valid window is considered because the window only shrinks when forced. O(n) time, O(1) space. Here the while runs at most once per step because zeros exceeds k by at most one, but write while anyway: the habit protects you on the problems where it does not.

Counting window: Find All Anagrams in a String, worked in full

Return every start index in s where a window of length len(p) is an anagram of p. The obvious solution compares Counter(s[i:i+k]) == Counter(p) at every i: O(n·k). Sliding a Counter and comparing two Counters each step is O(n·alphabet): acceptable, and fine to type first. The O(n) version keeps a difference map and a single integer saying how many characters are out of balance.

from collections import Counter

def find_anagrams(s, p):
    k = len(p)
    if k > len(s):
        return []
    need = Counter(p)                      # need[c] = count in p minus count in the window
    off = len(need)                        # how many characters have need[c] != 0

    def adjust(ch, delta):                 # keep `off` in step with `need`
        nonlocal off
        if need[ch] == 0:
            off += 1                       # was balanced, about to become unbalanced
        need[ch] += delta
        if need[ch] == 0:
            off -= 1                       # just became balanced

    for ch in s[:k]:                       # first window
        adjust(ch, -1)
    out = [0] if off == 0 else []
    for r in range(k, len(s)):
        adjust(s[r], -1)                   # character entering on the right
        adjust(s[r - k], +1)               # character leaving on the left
        if off == 0:
            out.append(r - k + 1)
    return out

Invariant: need[c] is the count of c in p minus its count in the current window, for every character, and off is the number of characters with a non-zero need. The window is an anagram exactly when off == 0. Each step does two O(1) adjustments, so O(n) time and O(alphabet) space. Dry-run on s = "cbaebabacd", p = "abc": answer [0, 6]. Edge: "abab", "ab" gives [0, 1, 2], overlapping windows count. Permutation in String is the same code returning True at the first hit.

If you type the simpler O(26·n) version, say what it costs and that a matched-letters counter makes each step O(1). That sentence is usually enough.

Prefix sums

prefix[i] is the sum of the first i elements, nums[:i], with prefix[0] = 0. Then the sum of nums[l..r] inclusive is prefix[r+1] - prefix[l]. One O(n) pass to build, O(1) per range query, O(n) space. Use it when there are many range queries or when the question is about subarrays and the elements can be negative.

Range Sum Query - Immutable

class NumArray:
    def __init__(self, nums):
        self.prefix = [0]                  # the empty prefix
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)
        # or: self.prefix = list(itertools.accumulate(nums, initial=0))

    def sum_range(self, left, right):      # inclusive on both ends
        return self.prefix[right + 1] - self.prefix[left]

O(n) build once, O(1) per query. Without the leading 0 you need a special case for left == 0; with it you do not. Say why the class exists: the array is immutable and queried many times, so paying O(n) once beats O(n) per query.

Product of Array Except Self: prefix and suffix passes

Division is forbidden (and would break on zeros). out[i] is the product of everything to the left of i times the product of everything to the right. Two passes, one running product each, written into the same output list.

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    run = 1
    for i in range(n):                     # pass 1: out[i] = product of nums[:i]
        out[i] = run
        run *= nums[i]
    run = 1
    for i in range(n - 1, -1, -1):         # pass 2: multiply by product of nums[i+1:]
        out[i] *= run
        run *= nums[i]
    return out

O(n) time, O(1) extra space beyond the output. Dry-run [1, 2, 3, 4]: after pass 1 [1, 1, 2, 6]; after pass 2 [24, 12, 8, 6]. With zeros the method is unchanged: [-1, 1, 0, -3, 3] gives [0, 0, 9, 0, 0].

Subarray Sum Equals K, worked in full

Count contiguous subarrays summing to k. Negatives are allowed, so a sliding window does not work (adding an element can make the sum go down). Reformulate: a subarray nums[j..i] sums to k exactly when prefix[i+1] - prefix[j] == k, that is prefix[j] == prefix[i+1] - k. So while scanning, for the current running sum ask "how many earlier prefix sums equal run - k". That is a dict lookup, the same lookup-before-insert pattern as Two Sum in topic 3.

def subarray_sum(nums, k):
    seen = {0: 1}                          # prefix sum → times seen; the empty prefix (sum 0) counts once
    run = 0
    count = 0
    for x in nums:
        run += x
        count += seen.get(run - k, 0)      # 1. look up: how many earlier prefixes make a sum of k ending here
        seen[run] = seen.get(run, 0) + 1   # 2. then record this prefix
    return count

Invariant: seen holds the frequency of every prefix sum for prefixes strictly before the current position, including the empty prefix. O(n) time, O(n) space in the worst case (all prefix sums distinct).

Why {0: 1}: a subarray starting at index 0 with sum k has run - k == 0, and the empty prefix is the one "earlier prefix" that matches. Without it, [1, 2, 3], k = 3 returns 1 instead of 2 (misses [1, 2]). Why lookup before insert: with k = 0, inserting first makes run - k == run match the entry you just added, counting an empty subarray at every position. [1, 2, 3], k = 0 would return 3 instead of 0. Test exactly those two cases out loud.

Pattern table

The same patterns on logs

Longest run of consecutive DOWN events per host

Records are host,status in observation order and hosts interleave. A single run counter is wrong because host b's DOWN would extend host a's run. Keep the run state per host: the read/write idea applied to a stream, with a dict instead of an index.

def longest_down_run(rows):                # rows: iterable of (host, status)
    cur = {}                               # host → length of the current DOWN run
    best = {}                              # host → longest run seen
    for host, status in rows:
        if status == 'DOWN':
            cur[host] = cur.get(host, 0) + 1
            best[host] = max(best.get(host, 0), cur[host])
        else:
            cur[host] = 0                  # UP resets only this host
            best.setdefault(host, 0)       # a host that is never DOWN still appears, with 0
    return best

Invariant: cur[h] is the length of the DOWN run that ends at h's most recent record; best[h] is the maximum cur[h] has reached. O(n) time, O(u) space for u hosts. Reading the rows from a file is topic 5's loop; this is lab 6. The follow-up "why does one global counter fail" wants the word "interleave".

Count 60-second windows with more than k errors

Given error timestamps sorted ascending, count the errors at which the trailing window [t - 60, t] contains more than k errors. A deque holds the timestamps currently inside the window; old ones fall off the left.

from collections import deque

def count_bursts(timestamps, k, window=60):
    q = deque()                            # timestamps within [t - window, t]
    bursts = 0
    for t in timestamps:
        q.append(t)
        while q[0] < t - window:           # WHILE: several events may expire at once
            q.popleft()
        if len(q) > k:
            bursts += 1
    return bursts

Invariant: after the while, the deque holds exactly the events with timestamp in [t - window, t]. Each timestamp is appended once and popped at most once: O(n) amortised, O(events per window) space. popleft on a deque is O(1); list.pop(0) would be O(n) and turn this into O(n²) (topic 11). The boundary is inclusive here: an event exactly 60 seconds old still counts. Say which you chose. Example: [0, 30, 50, 61, 200, 210, 215] with k = 2 returns 3 (at 50, 61 and 215).

Variants to be ready for. Per host: recent = defaultdict(deque) and run the same body on recent[host]; that is lab 10. Unsorted input: sort first, O(n log n), or bucket counts by second if the time span is small. Only the count is needed and the input is a list: a left index into the list replaces the deque; the deque is what you need when the input streams and per host.

Interview questions

Traps

• Shrinking a variable window with if instead of while. It passes the easy cases and fails the moment two removals are needed.
• Window length as right - left instead of right - left + 1, and range sum as prefix[right] - prefix[left] instead of prefix[right + 1] - prefix[left]. Both ends are inclusive; dry-run a window of length 1.
• Forgetting prefix[0] = 0 or seen = {0: 1}. Every subarray that starts at index 0 is missed.
• Inserting the current prefix sum before looking up run - k. With k = 0 it matches itself.
• Trying to assign into a string, or building the answer with += in a loop. Use a list and join.
• if x in some_list inside the loop: O(n) per check, O(n²) total. Use a set or dict. Same for list.pop(0) where a deque is needed.
• Slicing inside the loop (s[i:i+k], sum(nums[i:i+k])). Each slice is O(k); the whole loop becomes O(n·k). Slide the aggregate instead.
• Using the stale last-seen index without the >= left guard, which moves left backwards.
• Applying a sliding window to a sum problem with negative numbers. Reach for prefix sums.
• Not handling len(p) > len(s) before building the first window, or an empty input before sum(nums[:k]).

Do before marking this topic done

Blank editor, no running the code until you have dry-run it on paper, invariant said out loud before each loop.

1. Valid Palindrome both ways: the two-line version, then the O(1)-space two-pointer version. Test "A man, a plan, a canal: Panama", " ", ".,", "0P". Then answer "what about Unicode" (casefold, and isalnum is already Unicode-aware).
2. Move Zeroes and Merge Sorted Array. For each, write the invariant as a comment above the loop before writing the loop. Then merge two sorted lists into a new list front-to-front and say how it becomes lab 9.
3. Longest Substring Without Repeating Characters with the set and while, then with the last-seen dict. Dry-run both on "abba" and "tmmzuxt" (answers 2 and 5). Then Max Consecutive Ones III with the zero budget.
4. Find All Anagrams in a String with the off counter. Dry-run "cbaebabacd", "abc" to get [0, 6] and "abab", "ab" to get [0, 1, 2]. Then Maximum Average Subarray I in under three minutes.
5. Range Sum Query, Product of Array Except Self, Subarray Sum Equals K. For the last one, test [1, 2, 3], k = 3 (2) and [1, 2, 3], k = 0 (0), and explain which line each test protects. Then lab 6 and lab 10 from the prompts alone.

Practice: linked problems

Logged attempts feed the tracker. Open the problem in a new tab, solve in a blank editor, then log honestly.

• LC 88Merge Sorted ArrayEasy
• LC 125Valid PalindromeEasy
• LC 283Move ZeroesEasy
• LC 303Range Sum Query - ImmutableEasy
• LC 643Maximum Average Subarray IEasy
• LC 238Product of Array Except SelfMedium
• LC 3Longest Substring Without Repeating CharactersMedium
• LC 438Find All Anagrams in a StringMedium
• LC 560Subarray Sum Equals KMedium
• LC 1004Max Consecutive Ones IIIMedium

← 8 · TCP vs UDP: handshake, state, loss and congestion control · all topics · 10 · Switching: MAC learning, VLANs, STP and LAG →