Arrays, Strings, and Hashing Questions

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

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.

Direct answer

Compare the sum (and sum of squares) of the actual array against what a clean 1..n sequence would sum to; the two differences give you a system of two equations in the two unknowns (the missing value and the duplicate value), which you can solve directly. That approach is O(n) time and O(1) space, but it is vulnerable to integer overflow in fixed-width-integer languages, so a bitwise XOR-based approach is the more robust choice when overflow safety matters, at the cost of being noticeably less intuitive to derive on the spot.

Approach: sum and sum-of-squares

Let missing and dup be the two unknowns. Two quantities are cheap to compute from the array:

Dividing the second equation by the first isolates the other combination:

Now sum_diff gives missing - dup directly, and the division above gives missing + dup; adding and subtracting those two values solves for missing and dup individually.

Approach: XOR

1. XOR every value 1..n together with every value in nums. Every value that appears exactly twice (every correct value except missing and dup) cancels itself out via x ^ x == 0; missing (present once, from the 1..n side only) and dup (present three times total: twice in nums, once from the 1..n side, an odd count) survive, leaving missing ^ dup.
2. Find any bit where missing and dup differ (any set bit in missing ^ dup; the lowest set bit is a convenient, deterministic choice).
3. Partition both the 1..n range and nums by that bit, XOR each partition together; this isolates missing and dup into two separate accumulators (in some order).
4. One more pass, checking whether one of the two candidates actually occurs in nums, resolves which candidate is dup and which is missing.

Complexity

Both approaches: O(n) time, O(1) extra space. The sum approach is easier to derive but risks overflow on the squares term for large n in a fixed-width-integer language; the XOR approach never accumulates a value wider than the input values themselves, so it cannot overflow regardless of n.

Edge cases

• missing and dup adjacent in value (e.g. missing=3, dup=2): both approaches handle this with no special-casing.
• n = 1 isn't meaningfully defined for this problem (can't have both a missing and a duplicate value with a single slot), so this assumes n >= 2.

def missing_and_duplicate_sum(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    expected_sqsum = n * (n + 1) * (2 * n + 1) // 6
    actual_sum = sum(nums)
    actual_sqsum = sum(x * x for x in nums)

    sum_diff = expected_sum - actual_sum
    sqsum_diff = expected_sqsum - actual_sqsum

    sum_plus = sqsum_diff // sum_diff
    missing = (sum_diff + sum_plus) // 2
    dup = sum_plus - missing
    return missing, dup


def missing_and_duplicate_xor(nums):
    n = len(nums)
    xor_all = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    diff_bit = xor_all & (-xor_all)

    group_a = 0
    group_b = 0
    for i in range(1, n + 1):
        if i & diff_bit:
            group_a ^= i
        else:
            group_b ^= i
    for num in nums:
        if num & diff_bit:
            group_a ^= num
        else:
            group_b ^= num
    if nums.count(group_a) > 0:
        dup, missing = group_a, group_b
    else:
        dup, missing = group_b, group_a
    return missing, dup


nums = [1, 2, 2, 4]  # n=4; 3 is missing, 2 is duplicated
print(missing_and_duplicate_sum(nums))
print(missing_and_duplicate_xor(nums))

nums2 = [3, 1, 2, 5, 3]  # n=5; 4 is missing, 3 is duplicated
print(missing_and_duplicate_sum(nums2))
print(missing_and_duplicate_xor(nums2))

Output:

(3, 2)
(3, 2)
(4, 3)
(4, 3)

Both approaches agree on both test cases: (missing, dup) = (3, 2) for [1, 2, 2, 4], and (4, 3) for [3, 1, 2, 5, 3], confirming the algebra and the bitwise derivation independently reach the same answer.

Trade-offs and pitfalls

• Numerical stability (overflow), the question's specific ask: expected_sqsum grows roughly like $n^3/3$, so for large n (say, n around $10^9$ or larger, plausible for an ID-space-sized array) this can overflow a 32-bit or even 64-bit signed integer in a language with fixed-width arithmetic (C, C++, Java, Rust's default integer types), silently producing a wrong sqsum_diff and therefore a wrong answer with no error raised. Python itself has arbitrary-precision integers, so this specific overflow can't happen in Python, but a candidate should still name it, since the same algorithm is routinely implemented in fixed-width-integer languages, and "no overflow in Python" is not the same claim as "no overflow, period."
• The XOR approach sidesteps overflow entirely, since XOR never produces a value wider than the bit-width of the inputs themselves (unlike a running sum or sum-of-squares, which can grow arbitrarily large as more terms accumulate); this is the practical reason to prefer it once overflow is a real concern, at the cost of the derivation being considerably less obvious to reconstruct under interview pressure than "add up the differences."
• A common bug in the sum approach: using floating-point division for sum_plus, which can introduce rounding error for large n; integer division (//) is correct here because sqsum_diff is guaranteed to be evenly divisible by sum_diff (their ratio is missing + dup, an integer), so floor division is exact, not an approximation.
• A common bug in the XOR approach: picking the wrong bit to partition on (any set bit in missing ^ dup works, not just the lowest one, but it must be a bit where they actually differ), or forgetting the final disambiguation pass and returning (group_a, group_b) in an arbitrary, unverified order.

Direct answer

Add the two digit strings exactly the way long addition is done by hand: walk both strings from the rightmost digit, add the corresponding digits plus any carry from the previous position, keep the ones digit as the result and carry the tens digit forward, and continue until both strings and the carry are exhausted. This never converts the whole number into a native integer type, runs in O(max(len(a), len(b))) time and space, and generalizes directly to any base by changing how individual digits are parsed and re-emitted.

Structured elaboration

Why this can't just use native integer addition. The entire point of the exercise is that the numbers may be arbitrarily large decimal strings, potentially larger than any fixed-width integer type can represent without an arbitrary-precision ("big-int") library; the question explicitly disallows using one, so digits are processed as characters, not as a machine integer.

The right-to-left digit-pair-plus-carry loop. Two index pointers start at the last character of each string and move left. At each step, the digit from a (or 0 if that pointer has run past the start of a) is added to the digit from b (or 0, similarly) plus the carry from the previous step. The result's ones digit (total % 10) is appended to the output, and the new carry is the tens digit (total // 10). The loop continues as long as either pointer still has digits left, or a carry is still pending, which correctly handles the case where the final addition produces an extra leading digit (e.g. 9 + 9 = 18, carrying a new leading 1).

Reversal at the end. Because digits are produced from least-significant to most-significant (processing right to left), the accumulated digit list is in reverse order relative to the final answer and must be reversed once before joining into the output string.

Generalizing to base 16 or other bases. The algorithm's structure doesn't change at all between bases; only two things change: how a single character is parsed into its numeric digit value, and how a numeric digit value is turned back into a character. In decimal, int(digit) and str(digit) handle this. For an arbitrary base b (2 through 36), Python's int(digit, b) parses a single base-b digit character (handling both decimal digits and letters a through z for bases above 10), and indexing into a fixed alphabet string (\"0123456789abcdefghijklmnopqrstuvwxyz\") re-emits a digit value as its base-b character. The carry logic is identical, just with % base and // base replacing % 10 and // 10.

Worked example

Full runnable code with pinned test cases, including the question's own large-number example, verified against Python's own native big-integer addition as ground truth (used here only to cross-check the from-scratch implementation, not as a substitute for it):

def add_strings(a, b):
    """Add two non-negative decimal-string integers without big-int libs.
    O(max(len(a), len(b))) time and space, single right-to-left pass with
    a carry, exactly like manual long addition."""
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    digits = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i]) if i >= 0 else 0
        db = int(b[j]) if j >= 0 else 0
        total = da + db + carry
        digits.append(str(total % 10))
        carry = total // 10
        i -= 1
        j -= 1
    return ''.join(reversed(digits))


def add_strings_base(a, b, base):
    """Same algorithm generalized to an arbitrary base (2-36), using
    int(digit, base) to parse and a base-N string alphabet to re-emit."""
    digits_alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    out = []
    while i >= 0 or j >= 0 or carry:
        da = int(a[i], base) if i >= 0 else 0
        db = int(b[j], base) if j >= 0 else 0
        total = da + db + carry
        out.append(digits_alphabet[total % base])
        carry = total // base
        i -= 1
        j -= 1
    return ''.join(reversed(out))


if __name__ == "__main__":
    a = "9876543210123456789"
    b = "1234567890987654321"
    result = add_strings(a, b)
    expected_via_python_int = str(int(a) + int(b))
    print(f"add_strings({a!r}, {b!r})")
    print(f"  result   = {result}")
    print(f"  expected = {expected_via_python_int} (cross-checked via Python's native int addition)")
    print(f"  match: {result == expected_via_python_int}")

    more_tests = [
        ("0", "0", "0"),
        ("1", "9", "10"),
        ("99", "1", "100"),
        ("123", "0", "123"),
    ]
    for x, y, exp in more_tests:
        r = add_strings(x, y)
        print(f"add_strings({x!r}, {y!r}) = {r} (expected {exp})")

    hex_result = add_strings_base("ff", "1", 16)
    print(f"add_strings_base('ff', '1', 16) = {hex_result} (expected 100)")

Output (actual run):

add_strings('9876543210123456789', '1234567890987654321')
  result   = 11111111101111111110
  expected = 11111111101111111110 (cross-checked via Python's native int addition)
  match: True
add_strings('0', '0') = 0 (expected 0)
add_strings('1', '9') = 10 (expected 10)
add_strings('99', '1') = 100 (expected 100)
add_strings('123', '0') = 123 (expected 123)
add_strings_base('ff', '1', 16) = 100 (expected 100)

This confirms the question's own stated example: '9876543210123456789' + '1234567890987654321' -> '11111111101111111110' is correct, verified both by the character-by-character implementation and by cross-checking against Python's native arbitrary-precision integer addition on the same inputs. The base-16 example ('ff' + '1' = '100' in hex, i.e. 255 + 1 = 256) confirms the generalization: the carry chain propagates through both hex digits exactly as it would for 99 + 1 = 100 in decimal.

Trade-offs and pitfalls

• Converting both strings to native integers, adding, and converting back (str(int(a) + int(b))) is the obvious shortcut and was used above only as a cross-check, not as the answer: for genuinely arbitrary-precision inputs in a language without native big-int support (or under an explicit "no big-int library" constraint, as this question states), this shortcut isn't available at all, which is the entire point of the exercise.
• A common bug is forgetting the final carry: if the loop condition doesn't check carry as an independent continuation condition (only checking i >= 0 or j >= 0), an addition like 9 + 9 (which produces 18, needing an extra leading digit) silently drops the final carry digit.
• Building the result with repeated string concatenation (result = digit + result instead of appending to a list and reversing once at the end) works but is less efficient in languages or situations where string concatenation is O(current length) per operation, making a naive left-prepend approach O(n^2) overall instead of O(n); appending to a list and reversing once avoids this.
• This implementation assumes both inputs are non-negative digit strings with no sign character or leading-zero ambiguity beyond a literal "0"; supporting signed values would require detecting and handling a leading - or + before the digit-processing loop, which is a real but separate extension.
• The base generalization above supports bases 2 through 36 only, since it relies on Python's int(digit, base) and a 36-character alphabet; supporting arbitrary bases beyond 36 would require a different, explicitly-provided digit alphabet rather than reusing 0-9a-z.

Direct answer

Normalize both strings to the same Unicode normalization form and case-fold them, rather than just lowercasing, before counting characters. The same visual text can be represented by different underlying code point sequences, and case folding, not naive lowercasing, is the operation Unicode actually defines for caseless comparison across scripts. With that one extra normalization step, the same O(n) time, O(k) space frequency-map technique from the basic version still applies unchanged, k bounded by the number of distinct normalized characters.

Structured elaboration

Normalization forms. NFC (Normalization Form Canonical Composition, preferring a single precomposed character wherever one exists) and NFD (Normalization Form Canonical Decomposition, preferring a base character followed by separate combining marks) are two different, both entirely valid, code point sequences for the exact same visual text. "café" typed as a precomposed é is 4 code points; the same visual text with é written as "e" plus a combining acute accent is 5 code points. A character-by-character frequency count of the two, with no normalization step, sees different counts for literally identical text.

Casefold, not lower(). Python's str.lower() does not implement full Unicode case folding. The clearest example is German eszett: "straße".lower() leaves ß alone (still 6 characters), while "straße".casefold() expands it to "ss" (7 characters), which is the standard case-insensitive equivalence Unicode defines (ß case-folds to ss). casefold(), not lower(), is the correct building block for caseless comparison across languages.

Stated assumptions. This technique operates at the code point level after normalizing and case-folding, not at the full grapheme-cluster level (a base letter with several stacked combining marks, common in Vietnamese or Devanagari text, is a deeper case addressed only as a boundary note below, not solved here). str.isalnum() in Python is Unicode-aware across scripts, not an ASCII-only check, so it correctly drops whitespace and punctuation in non-Latin text too. Whichever normalization form you pick, NFC or NFD, must be applied consistently to both input strings, the specific form chosen does not matter as long as it is the same on both sides of the comparison.

Worked example

import unicodedata
from collections import Counter

def _normalize_for_anagram(x: str, form: str = "NFC"):
    x = unicodedata.normalize(form, x)
    x = x.casefold()
    return [c for c in x if c.isalnum()]

def is_anagram_unicode(s: str, t: str) -> bool:
    ns, nt = _normalize_for_anagram(s), _normalize_for_anagram(t)
    if len(ns) != len(nt):
        return False
    return Counter(ns) == Counter(nt)

cafe_nfc = "caf" + chr(0x00E9)
cafe_nfd = "caf" + chr(0x0065) + chr(0x0301)
print("NFC form code points:", [hex(ord(c)) for c in cafe_nfc])
print("NFD form code points:", [hex(ord(c)) for c in cafe_nfd])
print()

def is_anagram_naive(s, t):
    def normalize(x):
        return [c.lower() for c in x if c.isalnum()]
    ns, nt = normalize(s), normalize(t)
    return len(ns) == len(nt) and Counter(ns) == Counter(nt)

print(f"is_anagram_naive(NFC {cafe_nfc!r}, NFD {cafe_nfd!r})   = {is_anagram_naive(cafe_nfc, cafe_nfd)}  (WRONG: same text, flagged as non-anagram)")
print(f"is_anagram_unicode(NFC {cafe_nfc!r}, NFD {cafe_nfd!r})  = {is_anagram_unicode(cafe_nfc, cafe_nfd)}  (correct: same text -> True)")
print()

strasse = "stra" + chr(0x00DF) + "e"
print(f"{strasse!r}.lower()    = {strasse.lower()!r}  (len {len(strasse.lower())})")
print(f"{strasse!r}.casefold() = {strasse.casefold()!r}  (len {len(strasse.casefold())})")
print(f"is_anagram_naive({strasse!r}, 'strasse')   = {is_anagram_naive(strasse, 'strasse')}  (WRONG: length mismatch under .lower())")
print(f"is_anagram_unicode({strasse!r}, 'strasse')  = {is_anagram_unicode(strasse, 'strasse')}  (correct: casefold equates ss/eszett)")
print()

import random
base = "ΟΔΥΣΣΕΥΣ"
shuffled = list(base.casefold())
random.Random(42).shuffle(shuffled)
shuffled_str = "".join(shuffled)
print(f"shuffled multilingual case: {base!r} vs {shuffled_str!r}")
print(f"is_anagram_unicode -> {is_anagram_unicode(base, shuffled_str)} (expected True: same multiset of letters, just reordered and re-cased)")
other = "ΑΘΗΝΑ"
print(f"is_anagram_unicode({base!r}, {other!r}) -> {is_anagram_unicode(base, other)} (expected False)")

Output:

NFC form code points: ['0x63', '0x61', '0x66', '0xe9']
NFD form code points: ['0x63', '0x61', '0x66', '0x65', '0x301']

is_anagram_naive(NFC 'café', NFD 'café')   = False  (WRONG: same text, flagged as non-anagram)
is_anagram_unicode(NFC 'café', NFD 'café')  = True  (correct: same text -> True)

'straße'.lower()    = 'straße'  (len 6)
'straße'.casefold() = 'strasse'  (len 7)
is_anagram_naive('straße', 'strasse')   = False  (WRONG: length mismatch under .lower())
is_anagram_unicode('straße', 'strasse')  = True  (correct: casefold equates ss/eszett)

shuffled multilingual case: 'ΟΔΥΣΣΕΥΣ' vs 'σσυσυεοδ'
is_anagram_unicode -> True (expected True: same multiset of letters, just reordered and re-cased)
is_anagram_unicode('ΟΔΥΣΣΕΥΣ', 'ΑΘΗΝΑ') -> False (expected False)

The NFC-versus-NFD case is the sharpest demonstration: the same literal text "café", represented two different (both entirely valid) ways, is wrongly flagged as not an anagram of itself by a naive .lower()-plus-Counter check, and correctly flagged as one once both sides are normalized to the same form first. The eszett case shows the same pattern for casing: .lower() leaves the two strings at different lengths (a real bug, not a subtlety), while .casefold() correctly equates them. A genuine multilingual anagram (the Greek letters of "ΟΔΥΣΣΕΥΣ", deterministically shuffled with random.Random(42)) confirms the technique still does its actual job, correctly returning True for a real anagram and False against unrelated Greek text ("ΑΘΗΝΑ").

Trade-offs and pitfalls

Code-point-level comparison after normalization is the practical, standard-interview-depth answer, but it is not full grapheme-cluster equality: text that stacks multiple combining marks on one base character can, in principle, be grouped differently by two representations that both eventually normalize to the same NFC form by a different path. In practice NFC handles the overwhelming majority of real-world multilingual text correctly; fully grapheme-cluster-safe comparison is a further, rarely-needed step beyond what this answer implements.

Order matters: normalize first, then case-fold, not the reverse, and not .lower() after normalizing instead of .casefold(). Applying case-folding to whichever normalization form you've already settled on gives a consistent answer regardless of how the input arrived; mixing the order or substituting .lower() reintroduces exactly the bugs demonstrated above.

This machinery, normalize plus casefold, is the multilingual, standards-based extension of the same technique as plain .lower(). Reach for it specifically when the input is genuinely multilingual or user-generated text, not as the default on every anagram check, the plain version is simpler and sufficient for ASCII-only input.