Arrays, Strings, and Hashing Questions

Direct answer

Make two passes over the array without ever dividing. In the first pass, fill the output with the running PREFIX product (the product of everything to the left of each index). In the second pass, walk from the right and multiply each entry by a running SUFFIX product (the product of everything to the right of each index). After both passes, output[i] holds the product of every element except nums[i].

Structured elaboration

Approach

def product_except_self(nums):
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output


def naive_division(nums):
    """The disallowed shortcut, shown only to make its zero-element failure
    concrete rather than asserted: multiply everything once, then divide by
    each element in turn."""
    total = 1
    for x in nums:
        total *= x
    out = []
    for x in nums:
        if x == 0:
            out.append(None)  # division by the zero element is undefined
        else:
            out.append(total // x)
    return out

This is O(n) time (two linear passes) and O(1) extra space, not counting the output array itself, exactly as the question specifies, since only two running scalar accumulators (prefix and suffix) are kept alongside the output.

Why prefix and suffix products work, and why no division is needed

Every position i's answer is exactly (product of nums[0..i-1]) * (product of nums[i+1..n-1]), the product of everything strictly to the left, times the product of everything strictly to the right. The first pass computes and stores the left-hand factor for every index in one sweep (writing it into output[i] before nums[i] itself is folded into the running prefix). The second pass computes the right-hand factor the same way while sweeping backward, multiplying it directly into the value already stored. Because the two factors are built and combined without ever needing nums[i] itself in the final expression, this naturally avoids the "divide the total product by nums[i]" approach, which is both explicitly disallowed here and would break outright on any zero in the input (division by zero, or worse, silently wrong results if a naive implementation tries to special-case just one zero).

Leave-one-out features (the question's explicit ask)

The prefix/suffix accumulation pattern used here is the general technique behind computing a "leave-one-out" aggregate for every position without recomputing the whole aggregate from scratch each time. The most common leave-one-out feature in practice is a SUM (for example, "total spend across a group, excluding this member"), computed the same way with running prefix and suffix sums instead of products; the product version shown here applies the identical idea whenever the aggregate you need excluded is a product rather than a sum, for example computing a joint likelihood or a normalization factor across a set of independent factors while excluding one factor at a time.

Worked example

Executed with python3 s84.py (both functions defined above):

product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]
manual check: [24, 12, 8, 6]

Manually: excluding index 0 leaves 2*3*4=24; excluding index 1 leaves 1*3*4=12; excluding index 2 leaves 1*2*4=8; excluding index 3 leaves 1*2*3=6. All four match the function's output exactly.

product_except_self([1, 2, 0, 4]) = [0, 0, 8, 0]
naive division-based version on the same input = [0, 0, None, 0]  <- breaks on the zero element

With a zero present, every output except the one at the zero's own index is 0 (since every other output's product still includes the zero), while the output AT the zero's index is the product of everything else (1*2*4=8). A division-based approach (compute the total product, then divide by nums[i]) fails outright here: dividing by the zero element itself is undefined, shown above returning None rather than the correct value 8.

Trade-offs and pitfalls

• The division-based shortcut (multiply everything, then divide by nums[i] for each output) is both explicitly disallowed by the question and fundamentally broken the moment any element is zero; the executed comparison above makes this concrete rather than asserted.
• The two-pass prefix/suffix technique generalizes directly to any associative combining operation (sum, product, min, max, and so on) wherever a "leave-one-out" aggregate is needed without an inverse operation (subtraction for sum, division for product) available or safe to use.
• If the array can be very large and the values themselves can be large integers, the running prefix and suffix products can grow to very large magnitudes; in a fixed-width integer language (unlike Python's arbitrary-precision integers), this needs an explicit overflow check or a different numeric representation, which is worth naming even though Python itself does not hit this limit.

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

Walk through long once with a single pointer, and advance a second pointer into short only when the current character of long matches the character short is currently waiting for. If the pointer into short reaches the end before long runs out, every character of short was found in order, so short is a subsequence of long.

Structured elaboration

Approach

def is_subsequence(short, long):
    i = 0
    if not short:
        return True
    for ch in long:
        if i < len(short) and ch == short[i]:
            i += 1
        if i == len(short):
            return True
    return i == len(short)

Only one pass over long is made, and the pointer into short never moves backward, so the total work is O(n) where n is the length of long, matching the question's explicit complexity requirement. No extra data structure is needed since matching only ever needs to compare the CURRENT position of short against the current character of long.

Application context (the question's explicit ask)

This same one-pass check is the building block behind approximate matching and fuzzy token mapping: for example, checking whether a user's typed abbreviation could plausibly expand to a longer canonical term ("gcm" as a subsequence of "google cloud monitoring"), or filtering a large candidate list down to the ones that could still match a partially typed query, before applying a more expensive scoring step only to that smaller candidate set.

Worked example

Executed with python3 s83.py, five pinned cases including two explicit edge cases (empty short, empty long):

is_subsequence('abc', 'ahbgdc')     = True  expected=True  match=True
is_subsequence('axc', 'ahbgdc')     = False expected=False match=True
is_subsequence('', 'anything')      = True  expected=True  match=True
is_subsequence('abc', '')           = False expected=False match=True
is_subsequence('ace', 'abcde')      = True  expected=True  match=True

'abc' is found in order inside 'ahbgdc' (a, then b, then c, each appearing later than the last), so it returns True. 'axc' fails because after matching 'a', no 'x' appears anywhere later in 'ahbgdc', so the pointer into short never reaches the end.

Trade-offs and pitfalls

• The empty-short-is-always-a-subsequence edge case (is_subsequence('', 'anything') returning True) is easy to get backwards if the loop logic is written slightly differently; the explicit if not short: return True guard above makes this an intentional decision rather than an accident of how the loop happens to terminate.
• If this check needs to run many times against the SAME long string with many different short candidates, a smarter structure (precomputing, for each position and character, the next occurrence of that character) avoids repeating the full O(n) scan per query, at the cost of O(n * alphabet size) preprocessing; that preprocessing trade is only worth it when the number of queries against the same long string is large.
• This only answers yes/no. If the caller also needs the actual matched positions in long (for example, to highlight which characters satisfied the match), track and return the index list as the pointer advances, rather than just the boolean.

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

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.