Arrays, Strings, and Hashing Questions

Direct answer

Kadane's algorithm tracks the best sum ending exactly at the current index, resetting it whenever it goes negative, which gives O(n) time and O(1) extra space. Extend it with a couple of extra index variables to also recover the winning subarray's start and end, and treat an empty input as an explicit error rather than guessing a placeholder value.

Structured elaboration

• State. current_sum: best sum of a subarray ending at the current index. best_sum: best seen anywhere so far.
• Reset rule. If current_sum goes negative, it can never help a future subarray (adding a negative running total only hurts the next element), so restart at the current element. This is what makes the algorithm handle an all-negative array correctly, PROVIDED you initialize best_sum and current_sum with nums[0], not 0.
• The classic initialization bug. Initializing best_sum = 0 silently treats the empty subarray as a legal candidate. For an all-negative array like [-3, -1, -4, -1, -5], the true best NON-EMPTY subarray sum is -1 (the single element -1), but a 0-initialized version would wrongly report 0, implying an empty subarray beats every real one. Most interview phrasings (this one included) require a non-empty subarray, so seed with the first element.
• Recovering indices. Track current_start (where the current running sum began) alongside current_sum; whenever current_sum resets, current_start moves to the current index. Whenever current_sum beats best_sum, copy current_start and the current index into best_start/best_end.
• Empty array. There is no subarray to return, so raise explicitly rather than returning 0 or None, which would look like a valid (and wrong) answer to a caller who doesn't check.

Worked example

def max_subarray(nums):
    if not nums:
        raise ValueError("max_subarray: input array must be non-empty")

    best_sum = current_sum = nums[0]
    best_start = best_end = 0
    current_start = 0

    for i in range(1, len(nums)):
        if current_sum < 0:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]

        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = i

    return best_sum, best_start, best_end


def max_subarray_brute_force(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s > best:
                best = s
    return best


cases = [
    [-2, 1, -3, 4, -1, 2, 1, -5, 4],
    [-3, -1, -4, -1, -5],
    [5],
    [2, 2, 2],
]
for nums in cases:
    best_sum, start, end = max_subarray(nums)
    brute = max_subarray_brute_force(nums)
    print(f"nums={nums} -> best_sum={best_sum}, subarray={nums[start:end+1]}, indices=({start},{end}), brute_force={brute}")
    assert best_sum == brute

try:
    max_subarray([])
except ValueError as e:
    print(f"empty input raised ValueError as expected: {e}")
print("brute-force cross-check passed for all cases")

Output (executed, python3 s62_kadane.py, also cross-checked against an O(n^2) brute force for every case):

nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4] -> best_sum=6, subarray=[4, -1, 2, 1], indices=(3,6), brute_force=6
nums=[-3, -1, -4, -1, -5] -> best_sum=-1, subarray=[-1], indices=(1,1), brute_force=-1
nums=[5] -> best_sum=5, subarray=[5], indices=(0,0), brute_force=5
nums=[2, 2, 2] -> best_sum=6, subarray=[2, 2, 2], indices=(0,2), brute_force=6
empty input raised ValueError as expected: max_subarray: input array must be non-empty
brute-force cross-check passed for all cases

Trade-offs & pitfalls

• Seeding best_sum = 0 is the single most common bug on this problem; always test against an all-negative array to catch it (as above).
• Deciding whether the empty subarray is a legal answer is a real design decision, not a formality; state the assumption up front rather than let the code's default silently pick one.
• The state above is O(1) beyond the input, so it also works directly on a stream you can only scan once, but you cannot recover the ORIGINAL array's earlier indices after the fact unless you kept them as you went, which is exactly what current_start/best_start already do here at no extra asymptotic cost.
• A Java port of this same logic is a straightforward, mechanical translation (three int locals instead of Python variables, an explicit IllegalArgumentException in place of the ValueError); nothing about the algorithm changes across the two languages.

Direct answer

Sort the array, then fix each element in turn as the "anchor" and use a two-pointer scan over the remaining sorted suffix to find pairs that complete the triplet to zero, skipping over duplicate values at every level to avoid duplicate triplets. This runs in O(n^2) time (O(n log n) sort plus an O(n) two-pointer scan for each of n anchors) and O(1) extra space beyond the output and the sort itself. The same anchor-then-two-pointer idea generalizes to k-sum by recursing: fix one more element per level until only two remain, then solve that base case with two pointers.

Algorithm: 3Sum

1. Sort nums.
2. For each index i (the anchor), skip it if it's a duplicate of the previous anchor (nums[i] == nums[i-1]), which prevents emitting the same triplet-starting-value twice.
3. If nums[i] > 0, stop entirely: since the array is sorted, every remaining element is also non-negative, so no triplet starting here or later can sum to zero (unless all are zero, already handled by the anchor being the smallest of the three).
4. Two-pointer scan left = i+1, right = n-1 over the sorted suffix: if the three-element sum is 0, record it and advance both pointers past any duplicate values; if the sum is negative, advance left (need a larger value); if positive, retreat right (need a smaller value).

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    result = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Generalizing to k-sum

The pattern is: fix one element, reduce the target by its value, and recurse on k-1 with the remaining sorted suffix, until k == 2, at which point solve with the same two-pointer scan used above (which is really just 3Sum with the anchor already fixed by the outer recursion). Each recursive level still needs the duplicate-skip at its own position to avoid duplicate combinations, and a similar early-exit prune (if the smallest possible sum of the remaining k elements already exceeds the target, or the largest possible sum is already below it, stop).

def k_sum(nums, target, k):
    nums = sorted(nums)

    def helper(start, k, target):
        n = len(nums)
        if k == 2:
            res = []
            left, right = start, n - 1
            while left < right:
                total = nums[left] + nums[right]
                if total == target:
                    res.append([nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
            return res

        res = []
        for i in range(start, n - k + 1):
            if i > start and nums[i] == nums[i - 1]:
                continue
            for sub in helper(i + 1, k - 1, target - nums[i]):
                res.append([nums[i]] + sub)
        return res

    return helper(0, k, target)

This runs in O(n^(k-1)) time: each of the k-2 outer recursive levels contributes a factor of O(n), and the base case two-pointer scan is O(n), for a total of O(n^(k-1)). 3Sum is exactly this generalization with k=3.

Worked example

import itertools

def brute_force_k_sum(nums, target, k):
    nums_sorted = sorted(nums)
    seen = set()
    result = []
    for combo_idx in itertools.combinations(range(len(nums_sorted)), k):
        combo_vals = tuple(nums_sorted[i] for i in combo_idx)
        if sum(combo_vals) == target and combo_vals not in seen:
            seen.add(combo_vals)
            result.append(list(combo_vals))
    return sorted(result)

print(three_sum([-1, 0, 1, 2, -1, -4]))
k_sum_result = k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print(k_sum_result)

brute = brute_force_k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print("brute-force cross-check:", brute)
print("agree:", sorted(k_sum_result) == brute)

Output (verified by execution, and k_sum's results were independently cross-checked against a brute-force itertools.combinations scan over every k-subset of indices, so agreement is real validation, not the same logic checked twice):

[[-1, -1, 2], [-1, 0, 1]]
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
brute-force cross-check: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
agree: True

Tracing why [-1, -1, 2] and [-1, 0, 1] are the only two triplets on the sorted input [-4, -1, -1, 0, 1, 2]: anchor -4 (index 0) needs a pair summing to 4 from [-1,-1,0,1,2], and the two-pointer scan finds none (max reachable pair sum here is -1+2=1, which the pointers converge past without hitting 4). Anchor -1 (index 1) needs a pair summing to 1 from [-1,0,1,2]: the scan finds -1 and 2 first (giving [-1,-1,2]), then continues and finds 0 and 1 (giving [-1,0,1]). The next anchor is also -1 (index 2), but it's skipped as a duplicate of index 1's value, which is exactly what prevents [-1,-1,2] (or a duplicate [-1,0,1]) from being emitted twice.

Trade-offs and pitfalls

• The two duplicate-skip lines are the single most error-prone part of this problem. Skipping the anchor's duplicates prevents duplicate triplet-starts; skipping left/right duplicates after recording a match prevents duplicate triplet-ends. Missing either one produces a correct set of values but with duplicate entries in the output.
• The nums[i] > 0: break early exit is an optimization, not a correctness requirement for 3Sum specifically (target 0): once sorted, a non-negative anchor means the two-pointer scan can never reach a negative-enough sum to cancel it out to zero. For a general k-sum with a nonzero target, this prune needs to be a real bounds check (is the target reachable at all given the remaining sorted suffix's min/max possible sums), not just a sign check.
• k-sum's O(n^(k-1)) complexity grows fast: 4Sum is already O(n^3), and this approach stops being practical well before k gets large; for genuinely large k, a hash-map-based approach (precompute all pair sums for k/2 elements when k is even) trades space for a lower time exponent, at the cost of needing to dedupe combinations across the two halves.
• Common wrong turn: using a hash set of frozenset or sorted tuples to dedupe triplets after generating all of them (including duplicates) via brute force. This works but is O(n^3) or worse and defeats the purpose of the sorted two-pointer approach, which prevents duplicates from being generated in the first place rather than filtering them out afterward.

Direct answer

First precompute, for every substring s[i..j], whether it is a palindrome, by dynamic programming over increasing substring length (a substring is a palindrome if its two endpoints match and the substring strictly inside it is also a palindrome). Then run a second dynamic-programming pass where cut[i] is the minimum number of cuts needed to partition the prefix s[0..i] into palindromic pieces, trying every valid palindrome ending exactly at i as the final piece.

Structured elaboration

Step 1: the palindrome table

def build_palindrome_table(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                is_pal[i][j] = (length == 2) or is_pal[i + 1][j - 1]
    return is_pal

Filling by increasing length guarantees that whenever is_pal[i + 1][j - 1] is read, it was already computed on an earlier iteration (a shorter substring), which is exactly why this fill order is required rather than incidental.

Step 2: minimum cuts

def min_cut(s):
    n = len(s)
    if n <= 1:
        return 0
    is_pal = build_palindrome_table(s)
    cut = [0] * n
    for i in range(n):
        if is_pal[0][i]:
            cut[i] = 0
            continue
        best = i
        for j in range(1, i + 1):
            if is_pal[j][i]:
                best = min(best, cut[j - 1] + 1)
        cut[i] = best
    return cut[n - 1]

Total cost: O(n^2) time (the palindrome table fill and the cut computation are each bounded by the number of (i, j) pairs), O(n^2) space for the table plus O(n) for the cut array, matching what the question asks for.

Optimizations to reduce constant factors AND memory footprint (both parts of the question's explicit ask)

• Constant factor: pack each row of the boolean palindrome table into a single machine integer used as a bitset, one bit per column, instead of a Python list of booleans. Membership becomes a bit shift and mask instead of a list index and a full Python object lookup, and the table's memory footprint drops substantially since a machine integer packs many booleans per word, with identical asymptotic behavior:

def min_cut_bitset(s):
    """Same DP as min_cut, but each row of the palindrome table is packed
    into a single Python int bitset (bit j of rows[i] set iff s[i..j] is a
    palindrome) instead of a list of booleans."""
    n = len(s)
    if n <= 1:
        return 0
    rows = [1 << i for i in range(n)]
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length == 2 or (rows[i + 1] >> (j - 1)) & 1):
                rows[i] |= (1 << j)
    cut = [0] * n
    for i in range(n):
        if (rows[0] >> i) & 1:
            cut[i] = 0
            continue
        best = i
        for j in range(1, i + 1):
            if (rows[j] >> i) & 1:
                best = min(best, cut[j - 1] + 1)
        cut[i] = best
    return cut[n - 1]

I cross-checked this bitset-packed version against the plain version above; both are exercised together in the worked example below.

• Memory footprint: the cut array itself already only needs O(n) space, one integer per prefix length; the O(n^2) memory lives entirely in the palindrome table. If memory, not time, is the binding constraint, one option is to recompute "is s[j..i] a palindrome" on demand via a direct two-pointer character comparison instead of storing the full table, trading a higher constant-factor time cost (each on-demand check costs up to O(n) rather than O(1) table lookup) for O(1) extra space beyond the output. This is a genuine time-for-space trade, not a free win, and is only worthwhile once the O(n^2) table itself is the actual bottleneck resource for the input sizes involved.

Worked example

Executed with python3 s79.py (defining both min_cut and min_cut_bitset above), the plain and bitset-packed versions run on five pinned strings and cross-checked:

min_cut('aab'                 ) = 1   bitset_packed=1   agree=True
min_cut('a'                   ) = 0   bitset_packed=0   agree=True
min_cut('ab'                  ) = 1   bitset_packed=1   agree=True
min_cut('racecarxyzracecar'   ) = 4   bitset_packed=4   agree=True
min_cut('aabbc'               ) = 2   bitset_packed=2   agree=True

'aab' needs exactly 1 cut: split into 'aa' and 'b', both palindromes, using the minimum possible number of cuts (0 cuts would require the whole string to already be a palindrome, which 'aab' is not).

Trade-offs and pitfalls

• The O(n^2) palindrome table is unavoidable in this straightforward DP formulation; genuinely reducing the worst-case time below O(n^2) requires fundamentally different machinery for palindrome detection that belongs to a different topic's territory, not a small tweak to this approach.
• A common bug: filling is_pal[i][j] using is_pal[i + 1][j - 1] before that entry has actually been computed. The length-ordered fill above exists specifically to prevent this; iterating by row or column index instead of substring length silently reads stale (default False) values and produces wrong results for longer palindromes.
• Off-by-one in the cut recurrence: forgetting the base case where s[0..i] is itself a palindrome (0 cuts needed) is an easy miss, distinct from the general "minimize over every valid split point j" loop, and produces an answer that is too high by exactly one in cases where the whole prefix needs no cut at all.

Direct answer

The same running-sum Kadane's approach handles the all-negative edge case correctly as long as best_sum/current_sum are seeded with the first element rather than 0. Extending it to track the maximum PRODUCT subarray needs one extra piece of state: because multiplying by a negative number can flip the current running minimum into the new maximum, you must track both the max-ending-here AND the min-ending-here at every position, not just the max.

Structured elaboration

• Sum version, with indices. current_sum resets to nums[i] whenever it goes negative, current_start moves with it; whenever current_sum beats best_sum, copy current_start/i into best_start/best_end. Seeding with nums[0] (not 0) is what makes an all-negative array report its true best single (least-negative) element, instead of a wrong 0 implying an empty subarray won.
• Why product needs a second running value. For sums, dropping below zero is always bad, so resetting is safe. For products, a large NEGATIVE running product can become the best POSITIVE product the moment it's multiplied by another negative number. So at each index track both:
  • max_end = max(nums[i], max_end_prev * nums[i], min_end_prev * nums[i])
  • min_end = min(nums[i], max_end_prev * nums[i], min_end_prev * nums[i])
    and update the running best from max_end.
• Zero handling. Any product crossing a zero is zero, so a zero naturally resets both max_end and min_end toward nums[i] itself (one of the three candidates above is always nums[i] alone), acting as a partition point in the array.
• Index tracking, the part that's easy to get wrong. The start index of the winning chain at position i is not always "the same start as the previous max": a sign flip can pull in the MIN chain's start instead. Track max_start and min_start as two separate running indices, exactly parallel to max_end/min_end, and copy whichever one wins into the reported answer.

Worked example

def max_subarray_product(nums):
    if not nums:
        raise ValueError("max_subarray_product: input array must be non-empty")

    max_end, max_start = nums[0], 0
    min_end, min_start = nums[0], 0
    best, best_start, best_end = nums[0], 0, 0

    for i in range(1, len(nums)):
        x = nums[i]
        options = [
            (max_end * x, max_start),
            (min_end * x, min_start),
            (x, i),
        ]
        new_max, new_max_start = max(options, key=lambda t: t[0])
        new_min, new_min_start = min(options, key=lambda t: t[0])
        max_end, max_start = new_max, new_max_start
        min_end, min_start = new_min, new_min_start

        if max_end > best:
            best, best_start, best_end = max_end, max_start, i

    return best, best_start, best_end


def max_subarray_product_brute_force(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        p = 1
        for j in range(i, n):
            p *= nums[j]
            if p > best:
                best = p
    return best


product_cases = [
    [2, 3, -2, 4],
    [-2, 0, -1],
    [-2, 3, -4],
    [-1, -2, -3, 0, -1],
]
for nums in product_cases:
    p, a, b = max_subarray_product(nums)
    subarray = nums[a:b + 1]
    computed = 1
    for v in subarray:
        computed *= v
    brute = max_subarray_product_brute_force(nums)
    print(f"nums={nums} -> best_product={p}, subarray={subarray}, product(subarray)={computed}, brute_force={brute}")
    assert computed == p
    assert p == brute
print("brute-force cross-check (value) and subarray self-consistency check passed for all product cases")

Output (executed, python3 s63_kadane_product.py, cross-checked against an O(n^2) brute force for value AND against recomputing each claimed subarray's own product):

nums=[2, 3, -2, 4] -> best_product=6, subarray=[2, 3], product(subarray)=6, brute_force=6
nums=[-2, 0, -1] -> best_product=0, subarray=[-2, 0], product(subarray)=0, brute_force=0
nums=[-2, 3, -4] -> best_product=24, subarray=[-2, 3, -4], product(subarray)=24, brute_force=24
nums=[-1, -2, -3, 0, -1] -> best_product=6, subarray=[-2, -3], product(subarray)=6, brute_force=6
brute-force cross-check (value) and subarray self-consistency check passed for all product cases

The all-negative-adjacent case [-1, -2, -3, 0, -1] shows the flip directly: two negatives (-2, -3) multiply to the positive 6, which beats every other candidate even though the array is mostly negative numbers.

Trade-offs & pitfalls

• A real bug caught during verification, worth naming explicitly. A first draft of this function tracked only a single running start index (updated only when the code decided it was "restarting fresh"). It produced a technically-correct product VALUE (24, for [-2, 3, -4]) paired with a subarray ([3, -4]) that actually multiplies out to -12, not 24: the reported value and the reported subarray disagreed with each other. The fix is exactly the two-start-index tracking above; the way it was caught is by recomputing each claimed subarray's own product and asserting it equals the claimed answer, which is good general practice for any "return a value AND a supporting slice" problem.
• A zero divides the array into independent segments for the product version; the best answer can be a single zero if every other segment is negative-product.
• Products can overflow fixed-width integer types (Java int/long, C) on a long array of large-magnitude values; Python's arbitrary-precision integers hide this, but a real production port needs an overflow strategy (wider type, or switch to summing logs of absolute values and tracking sign separately).
• Taking the absolute value of the sum-version and reusing it is not a valid shortcut: the sum version's reset rule ("restart if negative") is specifically wrong for products, since it would throw away a large negative run that a later negative number could have flipped into the best answer.

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.