Arrays, Strings, and Hashing Questions

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

Normalize both strings the same way (lowercase, drop non-alphanumeric characters), then compare their character frequency counts. Building a frequency map is a single O(n) pass per string; sorting both normalized strings and comparing them is O(n log n). For long strings that gap is the entire reason to prefer the frequency map.

Structured elaboration

Normalizing. Filter each string down to lowercase alphanumeric characters only (c.isalnum()), dropping spaces and punctuation. This is a modeling decision worth stating out loud: taken completely literally, "Dormitory" and "dirty room" are not the same sequence of characters at all (different case, an extra space), the question's own instruction to ignore case and non-alphanumeric characters is what licenses treating them as equivalent.

Frequency map. Count occurrences of each normalized character in both strings (collections.Counter does this in one pass) and compare the two counts for equality. Two strings are anagrams exactly when every distinct character occurs the same number of times in both, which a Counter equality check verifies directly, in O(k) time to compare, where k is the number of distinct normalized characters, bounded by the alphabet rather than by n.

Sorting alternative. Sort both normalized character sequences and check they are identical; two strings are anagrams if and only if their sorted forms match. Correct, but O(n log n) because of the sort, versus O(n) for building and comparing frequency maps. For long strings, that difference in growth rate is exactly what "preferred... for long strings" is asking you to justify.

Cheap short-circuit. Compare lengths of the two normalized sequences first; a mismatch there proves non-anagram in O(1) (after the O(n) normalization pass), without needing to build either a sorted copy or a frequency map.

Worked example

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    def normalize(x: str):
        return [c.lower() for c in x if c.isalnum()]
    ns, nt = normalize(s), normalize(t)
    if len(ns) != len(nt):
        return False
    return Counter(ns) == Counter(nt)

from collections import Counter as _Counter

def _is_anagram_sorted_check(s, t):
    def normalize(x):
        return sorted(c.lower() for c in x if c.isalnum())
    return normalize(s) == normalize(t)

cases = [
    ("Dormitory", "Dirty Room", True),
    ("William Shakespeare", "I am a weakish speller", True),
    ("listen", "silent", True),
    ("hello", "world", False),
    ("A gentleman", "Elegant man", True),
    ("", "", True),
    ("a", "ab", False),
]
all_agree = True
for a, b, expected in cases:
    r = is_anagram(a, b)
    print(f"is_anagram({a!r}, {b!r}) = {r} (expected {expected})")
    if r != _is_anagram_sorted_check(a, b):
        all_agree = False
print()
print("all cases agree between frequency-map and sorting approaches, as expected."
      if all_agree else "MISMATCH between frequency-map and sorting approaches!")

Output:

is_anagram('Dormitory', 'Dirty Room') = True (expected True)
is_anagram('William Shakespeare', 'I am a weakish speller') = True (expected True)
is_anagram('listen', 'silent') = True (expected True)
is_anagram('hello', 'world') = False (expected False)
is_anagram('A gentleman', 'Elegant man') = True (expected True)
is_anagram('', '') = True (expected True)
is_anagram('a', 'ab') = False (expected False)

all cases agree between frequency-map and sorting approaches, as expected.

Every case, including the classic "William Shakespeare" / "I am a weakish speller" anagram and the empty-string edge case, matches expectation, and a parallel sorting-based implementation was run against the identical inputs and agreed with the frequency-map result on every one, confirming the two approaches are equivalent in correctness, differing only in complexity.

Trade-offs and pitfalls

Check the length mismatch before doing anything else; it is the cheapest possible rejection and avoids building a data structure you already know cannot match.

Sorting is still a reasonable, sometimes preferable, choice for very short strings, or when you need the sorted form anyway for something else (grouping many words by their sorted key, for instance): at small n, the constant-factor difference between O(n) and O(n log n) barely matters in practice, and the sorted form doubles as a canonical grouping key.

Stating your normalization rules explicitly is part of a senior answer here: "ignore case and non-alphanumeric characters" is a specific, narrower definition of anagram than the literal character-for-character one, and silently assuming it without saying so is a common way this question goes subtly wrong in an interview, even when the code itself is correct.

Direct answer

Make a single pass over the list and accumulate counts in a hash map (Python's collections.Counter, which is a dict subclass purpose-built for this): for each string, increment its entry by one. This is O(n) time, where n is the total number of strings processed, and O(u) extra space, where u is the number of unique strings, which for typical real-world data (repeated categorical values, tokens, log lines) is far smaller than n itself, keeping the approach both time- and memory-efficient at the "millions of items" scale the question asks about.

Structured elaboration

Why a hash map is the right tool here. Counting occurrences requires answering "have I seen this exact value before, and how many times" for each item, which is precisely the operation a hash map is built to do in O(1) average time per lookup/update. Building the count dict is therefore a single O(n) pass: for each string, look up its current count (defaulting to 0 if new) and increment it. Counter does exactly this internally and additionally provides convenience methods (most_common(), direct construction from an iterable) on top of a plain dict.

Time and space, stated precisely. Time is O(n) because every one of the n input strings is visited exactly once, and each hash map update is O(1) amortized. Space is O(u), the number of distinct strings, not O(n): a list with heavy repetition (say, a categorical column with only a handful of distinct values repeated millions of times) uses memory proportional to that handful of distinct values, not to the list's full length. This distinction between n (total items) and u (unique items) is the detail that actually matters for the "millions of items" framing in the question, since it is u, not n, that determines the dict's memory footprint.

Applying the same technique at a narrower grain: counting vowels in a string. The identical hash-based counting technique applies just as well one level down, to counting occurrences of specific characters within a single string rather than counting occurrences of whole strings within a list. A case-insensitive vowel count is the same idea: fold case first (so 'A' and 'a' count as the same vowel), then check each character against a fixed small set of vowels, incrementing a running total. Because the set of vowels is fixed and tiny (5 characters), this doesn't even need a full frequency dict. A simple counter check against a frozenset suffices, which is O(n) time (n = length of the single string) and O(1) extra space, since the vowel set's size never grows with input size.

Worked example

Full runnable code with pinned test cases, including the question's own example and the vowel-counting variant:

from collections import Counter


def string_frequencies(strings):
    """O(n) time (n = total strings), O(u) extra space (u = unique strings)."""
    return dict(Counter(strings))


def count_vowels(s, vowels=frozenset("aeiou")):
    """Same hash-based technique applied to characters of one string instead
    of elements of a list: case-insensitive vowel count, O(n) time, O(1)
    extra space (the vowel set has fixed size 5, independent of len(s))."""
    return sum(1 for ch in s.casefold() if ch in vowels)


if __name__ == "__main__":
    data = ['a', 'b', 'a', 'c', 'b', 'a']
    result = string_frequencies(data)
    print(f"string_frequencies({data!r}) = {result!r}")

    vowel_tests = [
        ("Hello World", 3),
        ("AEIOUaeiou", 10),
        ("xyz", 0),
        ("", 0),
        ("Interview", 4),
    ]
    for s, expected in vowel_tests:
        r = count_vowels(s)
        print(f"count_vowels({s!r}) = {r} (expected {expected})")

Output (actual run):

string_frequencies(['a', 'b', 'a', 'c', 'b', 'a']) = {'a': 3, 'b': 2, 'c': 1}
count_vowels('Hello World') = 3 (expected 3)
count_vowels('AEIOUaeiou') = 10 (expected 10)
count_vowels('xyz') = 0 (expected 0)
count_vowels('') = 0 (expected 0)
count_vowels('Interview') = 4 (expected 4)

The first line matches the question's own example exactly: ['a','b','a','c','b','a'] -> {'a': 3, 'b': 2, 'c': 1}. The count_vowels('Interview') case is worth naming explicitly: the capital I counts alongside the lowercase e, i, e, since .casefold() runs before the membership check, giving 4 total (I, e, i, e), matching a case-insensitive count rather than an ASCII-literal one.

Trade-offs and pitfalls

• Sorting the list first and counting runs of equal adjacent elements is a valid alternative, but costs O(n log n) time versus the hash map's O(n), and it also destroys the original ordering unless a copy is sorted separately; for "moderate lists (millions of items)" as the question specifies, the linear hash-map approach is the better default.
• Counter(strings) alone already returns a fully-functional mapping; wrapping it in dict(...) here is purely to return a plain, predictable type to a caller who may not want Counter-specific behavior (like its most_common() method or its handling of missing keys returning 0 instead of raising KeyError); either is a reasonable answer, and it's worth naming the trade-off rather than silently picking one.
• For truly massive inputs that don't fit in memory as a single Python list (as opposed to "millions of items," which a modern machine handles comfortably in RAM), the same technique still applies conceptually: replace strings with a generator/iterator and update a single running Counter one item (or one fixed-size chunk) at a time via .update(), instead of ever materializing the whole input as a list. Peak memory then holds only the current item or chunk plus the running counts, not the full input; the counting operation itself does not change, only how the input is fed into it.
• A frequency count over Unicode strings needs the same normalization awareness as any other string-identity comparison: two strings that look identical but differ in Unicode representation (composed versus decomposed accented characters) will be counted as different keys unless normalized first, which matters if the input list can contain non-ASCII text.
• For the vowel-counting variant specifically, .casefold() is the correct choice over .lower() for the same reason it matters in general caseless comparison: locale-independent, more aggressive folding handles edge cases like the German sharp s correctly, though for a fixed 5-character ASCII vowel set this distinction rarely changes the result in practice; naming .casefold() anyway signals the same caseless-comparison discipline that matters whenever a comparison needs to be genuinely Unicode-safe.

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

If every element is guaranteed non-negative, a sliding window works: grow the window's sum, and shrink from the left whenever the sum overshoots the target, because adding a non-negative element can only increase or hold the sum, so shrinking is guaranteed to monotonically decrease it. Once negative numbers are allowed, that monotonicity breaks, so the general solution instead tracks prefix sums in a hash map: if prefix[i] - prefix[j] == target, the subarray from j+1 to i sums to target, so scanning once while checking whether running_sum - target has been seen before as an earlier prefix sum finds the answer in O(n) time and O(n) space.

Positive-only case: sliding window

def subarray_indices_positive_only(nums, target):
    left = 0
    running = 0
    for right, val in enumerate(nums):
        running += val
        while running > target and left <= right:
            running -= nums[left]
            left += 1
        if running == target:
            return (left, right)
    return None

This relies entirely on non-negativity: shrinking the window (removing nums[left]) can only decrease running, so the while running > target loop is guaranteed to terminate at a sum that is <= target, and if it lands exactly on target, that's a valid answer. With negative numbers present, removing an element from the left could just as easily increase the running sum as decrease it, so there is no longer a reliable direction to shrink in.

General case (including negatives): prefix sum plus hash map

def subarray_indices_prefix_hashmap(nums, target):
    prefix_to_index = {0: -1}   # empty prefix (before index 0) sums to 0
    running = 0
    for i, val in enumerate(nums):
        running += val
        needed = running - target
        if needed in prefix_to_index:
            return (prefix_to_index[needed] + 1, i)
        if running not in prefix_to_index:
            prefix_to_index[running] = i
    return None

The {0: -1} seed entry is what lets a subarray starting at index 0 be found correctly: it represents "the prefix sum before any elements have been added is 0," so if running itself ever equals target, needed = running - target = 0 is already in the map, pointing to index -1, giving a correct start index of 0. The if running not in prefix_to_index guard only stores the first occurrence of each prefix sum, which is what guarantees the returned subarray is as long as possible from that starting point rather than an arbitrarily chosen one (though any correct pair satisfies "sums to target"; the problem only asks for existence, not the shortest or longest one).

Worked example

def brute_force_subarray_indices(nums, target):
    n = len(nums)
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s == target:
                return (i, j)
    return None

r1 = subarray_indices_positive_only([1, 2, 3, 4, 5], 9)
r2 = subarray_indices_prefix_hashmap([1, -1, 5, -2, 3], 3)
print(r1, " (brute-force cross-check:", brute_force_subarray_indices([1, 2, 3, 4, 5], 9), ")")
print(r2, " (brute-force cross-check:", brute_force_subarray_indices([1, -1, 5, -2, 3], 3), ")")

Output (verified by execution, both cross-checked against an O(n^2) brute-force reference that tries every contiguous subarray directly):

(1, 3)  (brute-force cross-check: (1, 3) )
(0, 3)  (brute-force cross-check: (0, 3) )

For [1, 2, 3, 4, 5], target 9: the window grows through [1], [1,2], [1,2,3] to [1,2,3,4] (sum 10), which overshoots; one shrink step drops the leading 1, bringing the sum to exactly 9 with the window now [2,3,4] (indices 1-3), which matches immediately, returning (1, 3). For [1, -1, 5, -2, 3], target 3: the running prefix sums as the scan proceeds are 1, 0, 5, 3 (indices 0-3), with needed = running - target at each step -2, -3, 2, 0. At i=3, needed = 0, which IS in the map, but crucially it maps to index -1 (the seed entry), not index 1 (where prefix sum 0 also occurs, at i=1, from 1 + -1 = 0): the if running not in prefix_to_index guard means that once index -1 claims prefix-sum 0, the later occurrence at index 1 is never allowed to overwrite it. So the match resolves to (-1 + 1, 3) = (0, 3), i.e., the subarray [1, -1, 5, -2], which does sum to 1 + -1 + 5 + -2 = 3.

Trade-offs and pitfalls

• The sliding window is NOT a valid fallback once any negative number can appear, even a single one. A frequent mistake is applying the two-pointer shrink logic to "mostly positive" data and only breaking on adversarial inputs; the moment even one negative value is possible, the general prefix-sum-plus-hashmap approach is required for correctness, not just performance.
• The {0: -1} seed entry is the single most commonly dropped detail. Without it, any subarray that must start at index 0 is silently missed, because there is no recorded "prefix sum before the array starts" to subtract against.
• Storing only the first occurrence of each prefix sum (via the if running not in prefix_to_index guard) is a deliberate choice, not an accident: if the problem instead asked for the shortest subarray summing to target, this is exactly right; if it asked for the count of subarrays summing to target (a related but different problem), the correct approach is to track counts, not indices, and accumulate every match rather than returning early on the first one.
• Return-value ambiguity: this implementation returns any one valid subarray's indices (existence), which matches what the question asks; a caller wanting all valid subarrays, or the shortest, or the count, needs a variant of this same prefix-sum idea, not a fundamentally different algorithm.