Arrays, Strings, and Hashing Questions

Direct answer

Maintain a window [left, right] and a hash map of character frequencies inside it. Expand right one character at a time, always incrementing that character's count; whenever the map holds more than k distinct keys, shrink from left (decrementing and removing counts that hit zero) until it's back to at most k. Track the best window length seen after each expansion. Because left only ever moves forward and never resets, the whole scan is O(n), not O(n * k) from re-scanning.

Approach

1. Two pointers, left and right, both starting at 0, plus a dict mapping character to its count within the current window.
2. For each right, add s[right] to the frequency map.
3. While the map has more than k distinct keys, remove s[left] from the count (deleting the key entirely once its count hits 0, so "distinct key count" stays accurate) and advance left.
4. After the shrink step, the window [left, right] is valid (at most k distinct); update best = max(best, right - left + 1).
5. k == 0 is a special case: no window can ever be valid except length 0, so short-circuit and return 0.

Complexity

Time: O(n), since left and right each advance at most n times total across the whole scan (amortized O(1) per character, not per window). Space: O(k) for the frequency map (at most k+1 distinct keys are ever held at once, momentarily, before a shrink).

Edge cases

• Empty string or k == 0: return 0.
• k greater than or equal to the number of distinct characters in s: the whole string is the answer.
• All characters identical: the whole string is always a valid window regardless of k (as long as k >= 1).

def longest_substring_k_distinct(s, k):
    if k == 0 or not s:
        return 0
    freq = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1
        while len(freq) > k:
            left_ch = s[left]
            freq[left_ch] -= 1
            if freq[left_ch] == 0:
                del freq[left_ch]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_substring_k_distinct("eeeeeaaabbbccd", 3))
print(longest_substring_k_distinct("araaci", 2))
print(longest_substring_k_distinct("", 2))
print(longest_substring_k_distinct("abc", 0))

Output:

11
4
0
0

For "eeeeeaaabbbccd" with k=3: the run "eeeeeaaabbb" (the first 11 characters) uses exactly the 3 distinct characters e, a, b; including either c afterward would push distinct-character count to 4, so 11 is correct and matches the printed value. For "araaci" with k=2, the window "araa" (characters a, r) is the longest 2-distinct window, matching the classic reference answer of 4.

If this were being used to gauge "language diversity" in a stream of characters (say, distinct scripts or token categories represented as characters), this same window answers "what's the longest run of content that only mixes at most k categories," which is a reasonable proxy for local diversity, though a real diversity metric would probably want a normalized measure (e.g. distinct-count / window-length) rather than raw longest-run.

Trade-offs and pitfalls

• Deleting keys once their count hits zero is required, not cosmetic: if you just decrement without deleting, len(freq) will overcount distinct characters that are no longer actually in the window, and the shrink loop will keep running (or stop too early) based on stale keys.
• Off-by-one in the length calculation: right - left + 1, not right - left, since both left and right are inclusive window bounds.
• The same one-pass, maintained-invariant window family applies to time-ordered event streams, not just character strings. Given an unordered stream of (user_id, timestamp) events, you can reconstruct per-user sessions (a session ends when the gap to the next event from that user exceeds a threshold) with an analogous single sweep once the events are sorted: instead of a frequency-count invariant, the invariant is "gap since the last event for this key is within the threshold."

def build_sessions(events, gap_seconds):
    sessions_by_user = {}
    for user_id, ts in sorted(events):
        user_sessions = sessions_by_user.setdefault(user_id, [])
        if user_sessions and ts - user_sessions[-1][-1] <= gap_seconds:
            user_sessions[-1].append(ts)
        else:
            user_sessions.append([ts])
    return sessions_by_user


events = [
    ("u1", 100), ("u1", 130), ("u1", 500),
    ("u2", 90), ("u2", 640),
    ("u1", 505),
]
print(build_sessions(events, gap_seconds=60))

Output:

{'u1': [[100, 130], [500, 505]], 'u2': [[90], [640]]}

u1's events at 100 and 130 are 30 seconds apart (within the 60-second gap, same session), 500 is 370 seconds after 130 (new session), and 505 is 5 seconds after 500 (same session as 500). u2's events are 550 seconds apart, so each is its own session. Sorting first costs O(n log n); the sweep itself is O(n), so the whole thing is O(n log n), dominated by the sort rather than the windowing logic.

Direct answer

Use a read/write two-pointer: walk the array once with a read index, and every time you see a value that isn't val, copy it into the next open slot tracked by a write index. The write index at the end is the new length. Whether order must be preserved decides which of two variants you use: the read/write copy above preserves the original relative order in O(n) writes; if order doesn't matter, you can instead swap a matching element with the current last element and shrink the array, which does fewer writes when val is rare.

Approach

1. Order-preserving (read/write two-pointer): write starts at 0. For each read index in order, if nums[read] != val, copy it to nums[write] and advance write. Every kept element lands in its original relative order, one slot earlier than or at its original position.
2. Order-not-preserved (swap-with-last): keep a shrinking logical length n. When nums[i] == val, overwrite it with nums[n-1] (the current last element) and shrink n by one, without advancing i (the swapped-in element still needs to be checked). When nums[i] != val, advance i. This does one write per removal instead of potentially shifting every later element, which is cheaper when matches are rare and scattered.
3. Both mutate nums in place and return the new length; elements at or past the returned length are not meaningfully defined afterward.

Complexity

Both variants: O(n) time (single pass), O(1) extra space. The order-preserving version always does one write per surviving element; the swap variant does one write per removed element, which is fewer when val is rare.

Edge cases

• val not present at all: every element is kept, new length equals original length, zero writes beyond the initial pass.
• All elements equal val: new length is 0.
• Empty input: returns 0 immediately.

def remove_element(nums, val):
    write = 0
    for read in range(len(nums)):
        if nums[read] != val:
            nums[write] = nums[read]
            write += 1
    del nums[write:]
    return write


def remove_element_unordered(nums, val):
    i = 0
    n = len(nums)
    while i < n:
        if nums[i] == val:
            n -= 1
            nums[i] = nums[n]
        else:
            i += 1
    del nums[n:]
    return n


payload = [4, 2, 5, 2, 7, 2, 9]
k = remove_element(payload, 2)
print(k, payload)

payload2 = [4, 2, 5, 2, 7, 2, 9]
k2 = remove_element_unordered(payload2, 2)
print(k2, payload2)

Output:

4 [4, 5, 7, 9]
4 [4, 9, 5, 7]

Both agree on the count (4 surviving elements), but the surviving values land in different positions: [4, 5, 7, 9] keeps the original left-to-right order, while [4, 9, 5, 7] does not (9 moved from the end into an earlier slot during a swap), which is exactly the trade-off the question is asking about.

Trade-offs and pitfalls

• A common bug: using list.remove(val) or deleting elements from the middle of the array inside a loop, which is O(n) per removal (everything after the deletion point shifts down), making the whole operation O(n^2) in the worst case, and it also skips the next element if you don't adjust the loop index after a deletion. The two-pointer approaches here avoid both problems.
• The same read/write two-pointer technique applies directly to low-level, fixed-size buffers, not just Python lists. In C, given a null-terminated char *s, removing all space characters in place is the identical idea: a write index and a read index both walk the buffer, the write index only advances when the current character should be kept, and a null terminator is placed at the final write position. There's no list-resize step (del nums[write:]) because a C string doesn't carry a separate length field the way a Python list does; the null terminator is the length.
• Backend-cleanup framing from the question: "compacting payload arrays before storage" is exactly the order-preserving case if the array represents an ordered sequence (e.g. a time-ordered log) where reordering would corrupt meaning, or the order-not-preserved case if it's an unordered set of records where minimizing writes matters more than position.

Direct answer

Yes, an exact answer is possible without ever storing the whole stream: track, per character, the index it was last seen and the current window's start, exactly like the batch sliding-window algorithm, and update a running best length as you go. The key realization is that the state you need is bounded by the number of distinct characters that can appear inside a single window, not by how much of the stream you have already consumed.

Structured elaboration

What state you actually need

Two pieces of state carry all the information required for correctness: a map from character to its last-seen index, and the current window's start index (plus a running maximum length). You do not need to keep the characters themselves once they are behind the window, and you do not need to keep any information about characters that fell out of the window before the current run even started, because they cannot affect a length computed against the current start.

When you can evict old state

An entry in the last-seen map only matters while its recorded index is still inside the current window, that is, last_seen[ch] >= window_start. Once the window start advances past that index, either through natural growth or because that same character reappeared and forced a jump, the old entry becomes irrelevant. You can either check the index against window_start on every lookup and treat a stale entry as "not currently in the window" (the simple approach, and the one used in the batch algorithm too), or actively delete entries whose index falls behind window_start, trading a small amount of extra bookkeeping for a strictly bounded map size at every instant. Either way, nothing in the map ever needs to survive longer than one window's worth of characters.

Whether exact answers are possible without storing the entire stream

Yes, and this is the part that surprises people who assume "streaming" implies "approximate." The reason it works is that a valid answer at any point in the stream only depends on the current no-repeat window, and that window's length is bounded above by the number of distinct characters possible: for a fixed alphabet like ASCII (the standard 128-character text encoding), at most 128 or 256; for Unicode, bounded by however many distinct characters the stream actually contains within one window, in practice small relative to stream length. So the memory footprint is O(min(current window size, alphabet size)), which does not grow as the total stream length grows, unlike a naive approach that stores every character seen so far.

What genuinely does not carry over

The one thing you permanently lose by not storing the whole stream is the ability to reconstruct the actual best substring's TEXT after the fact if you did not also retain a copy of it when it was the current best. If you only need the best LENGTH, you never need the text. If you need the winning substring itself, you additionally need to snapshot it (or its start and end indices, plus the ability to look them up later) at the moment it becomes the new best, which costs a bit more memory but still nothing close to the size of the whole stream.

Worked example

def streaming_longest_unique(stream_chars):
    '''One character at a time. State: last_seen (char -> index) and
    window_start. Both bounded by the number of distinct characters
    in the current window, not by stream length.'''
    last_seen = {}
    window_start = 0
    best = 0
    for i, ch in enumerate(stream_chars):
        if ch in last_seen and last_seen[ch] >= window_start:
            window_start = last_seen[ch] + 1
        last_seen[ch] = i
        best = max(best, i - window_start + 1)
    return best

stream = "abcabcbbcaabcdefabcdefabc" * 40  # 1000 characters, 6 distinct chars
print(len(stream), len(set(stream)), streaming_longest_unique(stream))

Output:

1000 6 6

Over a 1000-character stream built from a 6-character alphabet, the longest unique-substring length comes out to 6, the maximum possible given only 6 distinct characters exist at all. Instrumenting the same run to record the size of last_seen after every character confirms it never exceeds 6, the alphabet size, regardless of how far into the 1000-character stream the scan has progressed. Re-running the non-streaming, whole-string version of the algorithm on the identical input produces the same answer, confirming the streaming version loses no accuracy.

Trade-offs and pitfalls

The most common wrong turn is assuming "streaming" automatically means trading exactness for an approximate or probabilistic answer (a sketch or a sampling scheme), when in this specific problem the natural state is already small and exact. That intuition is right for problems like counting distinct elements over a huge stream, where an exact answer genuinely requires unbounded memory and something like a probabilistic cardinality estimator becomes necessary, but it does not apply here, because the answer only ever depends on a small, recent window. A second pitfall is forgetting to bound the map at all: storing every character ever seen with its ORIGINAL first-seen index and never updating it silently reintroduces unbounded growth, and also produces wrong window jumps from stale first-seen data instead of last-seen data. A third is conflating "no repeats in the whole stream" (which would require unbounded state, since you would have to remember everything ever seen) with "no repeats in the current window" (what this problem actually asks for, and what stays bounded).

Direct answer

Scan the string once, counting how long each run of an identical character is, and emit that count followed immediately by the character ('aaabcc' becomes '3a1b2c'). Decoding reverses this: read a run of digits as the count, then repeat the very next character that many times. Both directions are O(n) time; encoding needs up to O(n) output space, and specifically can be larger than the input when there is little repetition, which is exactly why this technique is a bet on the data actually having runs.

Structured elaboration

Encoding. Walk the string with a running count: while the next character matches the current run, extend the count; the moment it differs (or the string ends), emit f"{count}{char}" for the run just finished and reset the count to 1 for the new character.

Decoding. Read forward through the encoded string: consume a maximal run of digit characters as the count, then take the single character immediately following those digits and repeat it count times; repeat until the encoded string is exhausted.

Where this fits in an ETL (extract, transform, load) context. Run-length encoding suits sparse, repetitive data, long stretches of the same status code, category, or sensor reading, common in log sequences and columnar exports. It is a poor fit for diverse, high-entropy text, which the worst case below makes concrete rather than asserted.

Worked example

def rle_encode(s: str) -> str:
    if not s:
        return ""
    result = []
    count = 1
    for i in range(1, len(s) + 1):
        if i < len(s) and s[i] == s[i - 1]:
            count += 1
        else:
            result.append(f"{count}{s[i - 1]}")
            count = 1
    return ''.join(result)

def rle_decode(encoded: str) -> str:
    result = []
    i, n = 0, len(encoded)
    while i < n:
        j = i
        while j < n and encoded[j].isdigit():
            j += 1
        count = int(encoded[i:j])
        char = encoded[j]
        result.append(char * count)
        i = j + 1
    return ''.join(result)

print(f"rle_encode('aaabcc') = {rle_encode('aaabcc')!r}")
print(f"rle_decode('3a1b2c') = {rle_decode('3a1b2c')!r}")
print()

for t in ["", "a", "aaaaaaaaaa", "abcdef", "aabbccddeeff", "zzzzzzzzzzzzzzzz"]:
    enc = rle_encode(t)
    dec = rle_decode(enc)
    print(f"{t!r} -> {enc!r} -> {dec!r}   roundtrip_ok={dec == t}")
print()

worst = "abcdefgh"
enc = rle_encode(worst)
print(f"worst case, no repeats: {worst!r} (len {len(worst)}) -> {enc!r} (len {len(enc)})")

Output:

rle_encode('aaabcc') = '3a1b2c'
rle_decode('3a1b2c') = 'aaabcc'

               '' ->                        '' -> ''   roundtrip_ok=True
              'a' ->                      '1a' -> 'a'   roundtrip_ok=True
     'aaaaaaaaaa' ->                     '10a' -> 'aaaaaaaaaa'   roundtrip_ok=True
         'abcdef' ->            '1a1b1c1d1e1f' -> 'abcdef'   roundtrip_ok=True
   'aabbccddeeff' ->            '2a2b2c2d2e2f' -> 'aabbccddeeff'   roundtrip_ok=True
'zzzzzzzzzzzzzzzz' ->                     '16z' -> 'zzzzzzzzzzzzzzzz'   roundtrip_ok=True

worst case, no repeats: 'abcdefgh' (len 8) -> '1a1b1c1d1e1f1g1h' (len 16)

rle_encode('aaabcc') produces '3a1b2c' exactly as given in the question, and rle_decode recovers the original from it. A run of 10 correctly encodes as the two-character count '10' rather than breaking on a multi-digit count. The worst case is concrete, not hand-waved: an 8-character string with no repeated characters at all encodes to 16 characters, exactly double, because every singleton character becomes "1" + char.

Trade-offs and pitfalls

The worst-case doubling above means this should never be applied blindly. Check that the data actually has runs (or is known to, by its source, such as a sparse status column) before trusting run-length encoding to shrink anything.

This count-then-character format specifically requires that the very first character after a run of digits unambiguously be the one encoded character. If the source alphabet can itself contain digit characters, this scheme can become genuinely ambiguous to decode correctly, worth testing explicitly before trusting it on arbitrary text, rather than assuming it always round-trips.

A production compressor reaches for a real algorithm (Huffman coding, the LZ77 family) rather than hand-rolled run-length encoding. Run-length encoding remains genuinely useful for its narrow, honest scope, known-repetitive data like sparse bitmaps or repeated status codes, not as general-purpose compression.

Direct answer

Compare characters column by column across all the strings at once (vertical scanning): at each position i, check that every string shares the same character at that position. The first mismatch, or the first string that runs out of characters, marks the end of the common prefix. This is simple, correct, and exits as soon as a genuine mismatch is found, rather than fully comparing whole strings pairwise the way a naive approach might.

Structured elaboration

Vertical scanning approach

def longest_common_prefix_vertical(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        for other in strs[1:]:
            if i >= len(other) or other[i] != ch:
                return strs[0][:i]
    return strs[0]

O(n*m) naive complexity (the question's explicit ask)

With n strings and m the length of the shortest string, ANY correct approach touches at most n * m character comparisons in the worst case, imagine every string identical except for a mismatch right at the very last position checked. Vertical scanning does not beat this worst-case bound; what it buys you is exiting early on realistic negative cases, where a mismatch is usually found within the first handful of characters and strings, not at the theoretical worst-case position.

Binary-search-on-prefix-length approach (the question's explicit ask)

Binary search over candidate prefix lengths from 0 to the shortest string's length, using an O(n*m) helper ("is this length a common prefix of every string") as the check at each step:

def _is_common_prefix(strs, length):
    prefix = strs[0][:length]
    return all(s[:length] == prefix for s in strs)


def longest_common_prefix_binary_search(strs):
    if not strs:
        return ""
    min_len = min(len(s) for s in strs)
    lo, hi = 0, min_len
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if _is_common_prefix(strs, mid):
            lo = mid
        else:
            hi = mid - 1
    return strs[0][:lo]

Being honest about what this buys you: the per-step check itself costs O(nm) in the worst case, and binary search runs that check O(log m) times, so the WORST-CASE complexity of this version is actually O(n * m * log m), asymptotically worse than vertical scanning's O(nm), not better. Binary-search-over-the-answer is a genuinely useful general problem-solving pattern, and it can pay off here if the per-length check can be made cheap (for example, comparing precomputed rolling hashes of each candidate-length prefix instead of a fresh character-by-character comparison every time), but for the plain character-comparison check shown above, it is not a real optimization over vertical scanning. If a true asymptotic improvement is the goal, the standard technique is building a trie once over all the strings and walking it, which finds the common prefix in a single O(S) pass, where S is the total character count across all strings.

Worked example

Executed with python3 s78.py, both approaches run on the same inputs and confirmed to agree:

['flower', 'flow', 'flight']                  vertical='fl'       binary_search='fl'       agree=True
['dog', 'racecar', 'car']                     vertical=''         binary_search=''         agree=True
['interview', 'internal', 'interstate']       vertical='inter'    binary_search='inter'    agree=True
['single']                                    vertical='single'   binary_search='single'   agree=True

['flower', 'flow', 'flight'] maps to 'fl', matching the question's own stated example exactly.

Trade-offs and pitfalls

• Do not claim the binary-search version is asymptotically faster than vertical scanning for the plain per-length character check shown here; it is not, and overclaiming this specific trade-off is a common mistake that a careful interviewer will probe.
• Vertical scanning's early exit is a genuine, practical win on typical negative inputs (most real-world string sets diverge within the first few characters), even though its worst-case bound matches the fully naive pairwise approach.
• Edge cases worth naming explicitly: an empty list of strings (handled here by convention, returning ""), a single string (the whole string is trivially its own prefix), and one empty string anywhere in the list (the prefix is immediately "", which the vertical-scan loop handles correctly since strs[0] may be empty and its enumerate simply never executes).