Arrays, Strings, and Hashing Questions

Direct answer

Precompute a running-total array prefix where prefix[i] is the sum of the first i counts, built once in O(n). Any inclusive range sum [left, right] is then prefix[right + 1] - prefix[left], O(1). When a new minute of events arrives, append one new prefix entry (last + new_count) in O(1) rather than recomputing anything. A "last W minutes" query is just a range-sum query where the range is derived from the current length, so it reuses the same O(1) machinery.

Approach

1. Build: prefix = [0]; for each count in order, append prefix[-1] + count. prefix has n+1 entries so that prefix[0] = 0 represents "the sum of zero elements," letting the range-sum formula work uniformly even for a range starting at index 0.
2. Range query [left, right] inclusive: prefix[right + 1] - prefix[left]. This is O(1) regardless of range width, because the two boundary lookups already encode the running total up to each endpoint.
3. Streaming update: appending a new minute's count is prefix.append(prefix[-1] + new_count), O(1) amortized (Python list append), since it only ever adds one new entry using the existing last total; nothing earlier in prefix needs to change. This is what makes the update efficiently incremental: each new event only costs one addition, never a recomputation of the whole array.
4. Windowed query ("last W minutes"): since the array is indexed one entry per minute in arrival order, the last W minutes are just the range [n - W, n - 1] (clamped to 0 if W exceeds the history length), so this reuses the same O(1) range-sum formula directly.

Complexity

Build: O(n) time, O(n) space for the prefix array. Range query: O(1). Streaming append: O(1) amortized. Windowed query: O(1), same as any other range query, because the window boundary is derivable directly from the current array length.

Edge cases

• Windowed query wider than the history so far (e.g. asking for the last 60 minutes when only 5 minutes of data exist): clamp the left boundary to 0 rather than going negative, returning the sum of everything available.
• Zero-length range (left == right + 1, i.e. querying an empty window): returns 0 correctly, since prefix[right+1] - prefix[left] collapses to prefix[left] - prefix[left].

class MinuteEventCounter:
    def __init__(self, counts):
        self.prefix = [0]
        for c in counts:
            self.prefix.append(self.prefix[-1] + c)

    def range_sum(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

    def append(self, count):
        self.prefix.append(self.prefix[-1] + count)

    def last_window_sum(self, window_minutes):
        n = len(self.prefix) - 1
        left = max(0, n - window_minutes)
        return self.range_sum(left, n - 1)


counts = [10, 0, 5, 20, 3]
counter = MinuteEventCounter(counts)

print(counter.range_sum(0, 4))
print(counter.range_sum(2, 3))

counter.append(7)
print(counter.range_sum(0, 5))

print(counter.last_window_sum(3))
print(counter.last_window_sum(60))

Output:

38
25
45
30
45

Five minutes of counts [10, 0, 5, 20, 3] sum to 38 overall, and minutes 2-3 (5 + 20) sum to 25, both matching the range-sum formula directly. After a sixth minute (7 events) streams in, the full six-minute sum is 45. The last-3-minutes window covers minutes 3, 4, 5 (20 + 3 + 7 = 30); asking for a 60-minute window when only 6 minutes of history exist correctly clamps to the whole history's sum, 45.

Trade-offs and pitfalls

• This O(1)-per-minute update relies on the array being indexed one entry per minute, in order, with no gaps (exactly the shape given in the question). If events instead arrived with irregular or sparse timestamps (not one guaranteed entry per minute) and a windowed query meant "events from timestamp T-60min to now" rather than "the last 60 array slots," you would need to look up the index corresponding to a given timestamp first, which is a binary search over a parallel timestamps array (O(log n)), not O(1); the O(1) windowed-query property here is a direct consequence of the question's stated per-minute indexing, not something that survives arbitrary timestamp irregularity for free.
• Prefix sums do not support efficient updates to a value that has already been counted (e.g. correcting minute 2's count after the fact): that would require rebuilding every later prefix entry (O(n)) with this simple array, whereas a Fenwick tree (binary indexed tree) supports both point updates and prefix queries in O(log n) each, at the cost of noticeably more implementation complexity than this straight prefix array. For a purely append-only stream (as asked here), the simple array is the right level of machinery; reach for a Fenwick tree only once in-place corrections to historical counts become a real requirement.
• Memory grows without bound on an infinite append-only stream: since every new minute keeps a running prefix entry forever, a long-lived service would eventually want to either cap the retained history (e.g. only keep the last 24 hours of prefix entries, discarding older ones once no query can reference them) or periodically "re-base" by dropping fully-expired history and adjusting subsequent range-sum math accordingly.

Direct answer

Sort the intervals by their start value, then sweep through them once, keeping a running "last merged interval": if the next interval's start is at or before that interval's end (an overlap, or an exact touch), extend the running interval's end to cover it; otherwise, the next interval begins a new, separate merged interval. This is O(n log n) time, dominated entirely by the initial sort, and O(n) space for the output.

Structured elaboration

Why sort by start first. Without imposing an order, a single forward pass cannot be trusted to have already seen every interval that might overlap the one currently being examined; an interval appearing later in the input array could easily start earlier than one already processed. Sorting by start guarantees that once the sweep has moved past a given point, every remaining interval starts at or after it, which is exactly what makes a single linear sweep afterward sufficient.

The merge step itself. Initialize the output with the first (now sorted) interval. For each subsequent interval [s, e], compare s against the END of the last interval currently in the output. If s <= last.end, the two intervals overlap or exactly touch, so extend the last interval's end to max(last.end, e), using max rather than just assigning e directly, because a later interval can be fully NESTED inside the one already being extended (a smaller end than the current running interval), and assigning e unconditionally would incorrectly shrink coverage that the merged interval already legitimately spans. If s > last.end, there is a genuine gap, and [s, e] starts a new entry in the output.

Complexity. The sort is O(n log n) and dominates the total cost; the sweep afterward visits each interval exactly once, O(n). The output requires O(n) space in the worst case (no intervals overlap at all, so every input interval becomes its own output entry).

Touching versus overlapping, a design decision worth naming. Whether two intervals that exactly touch (one's end equals the next one's start, such as [1,4] and [4,5]) should merge is a real semantic choice, not an automatic consequence of the algorithm. Using <= in the overlap check treats a touch as mergeable (matching how meeting-room-style problems usually intend adjacency: back-to-back meetings occupy no coverage gap), while a strict < would keep them as separate, back-to-back intervals; a senior answer should state explicitly which convention is being used rather than leave it implicit.

Worked example

def merge_intervals(intervals):
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda pair: pair[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))

# Independent cross-check: a genuinely different method (an event-counting sweep
# line) rather than a second copy of the same merge logic.
def sweep_line_reference(intervals):
    if not intervals:
        return []
    events = []
    for s, e in intervals:
        events.append((s, 0, 1))   # start: delta +1, processed before ends at same coord
        events.append((e, 1, -1))  # end:   delta -1
    events.sort()
    result = []
    active = 0
    run_start = None
    for pos, _, delta in events:
        if active == 0 and delta == 1:
            run_start = pos
        active += delta
        if active == 0:
            result.append([run_start, pos])
    return result

import random
random.seed(3)
hand_picked = [
    [[1, 4], [4, 5]],             # touching intervals
    [[5, 8], [1, 3]],             # unsorted input
    [[2, 5], [1, 10]],            # fully nested interval
    [[1, 2]],                     # single interval
    [],                           # empty input
    [[5, 6], [1, 2]],             # unsorted, non-overlapping
    [[1, 3], [2, 6], [8, 10], [15, 18]],
]
mismatches = 0
for tc in hand_picked:
    if merge_intervals(tc) != sweep_line_reference(tc):
        mismatches += 1
for _ in range(3000):
    n = random.randint(1, 6)
    intervals = [[a, a + random.randint(0, 5)] for a in (random.randint(0, 15) for _ in range(n))]
    if merge_intervals(intervals) != sweep_line_reference(intervals):
        mismatches += 1
print(f"7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = {mismatches}")

Output:

[[1, 6], [8, 10], [15, 18]]
7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = 0

matching the question's own example exactly: [1,3] and [2,6] overlap (2 <= 3) and merge into [1,6]; [8,10] and [15,18] each start after the previous merged interval's end, so they remain separate. This was additionally cross-checked against the independently-implemented sweep-line reference above (treating each interval as a +1/-1 event at its start/end and rebuilding runs where the event count returns to zero), which is a genuinely different method rather than a second copy of the same merge logic, on 7 hand-picked cases (touching intervals, unsorted input, a fully nested interval, a single interval, empty input, and unsorted non-overlapping intervals) plus a 3,000-trial random sweep (seed 3); the printed line confirms zero mismatches across all of it, giving real cross-validation rather than testing the code against itself.

Trade-offs and pitfalls

The most consequential bug is assigning last[1] = end directly instead of last[1] = max(last[1], end) when merging: this passes every test case where intervals only partially overlap or extend each other, and only fails on a fully nested interval, which is easy to omit from a quick manual test set and then breaks silently in production by shrinking coverage that should have been preserved. A second common bug is skipping the initial sort, either because the candidate assumes input is already given in start order (sample inputs in problem statements are often, misleadingly, already sorted) or forgets that an unsorted input makes a single forward sweep unreliable; always sort explicitly rather than relying on an assumption about input order. Finally, treat the touching-versus-overlapping boundary as a decision to state out loud (<= merges touching intervals, < does not) rather than an arbitrary implementation detail, since which one is correct depends on what the intervals represent.

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

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

Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.

Structured elaboration

Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.

Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.

Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.

Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.

Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.

Worked example

Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):

import unicodedata
from collections import Counter


def normalize_for_compare(s):
    """NFC-normalize then casefold. Length check must happen AFTER this,
    never on the raw string (see the STRASSE case below)."""
    return unicodedata.normalize("NFC", s).casefold()


def is_anagram(s, t):
    """O(n) time, O(k) extra space where k is the distinct-character count,
    counting-based rather than sorting-based."""
    s_norm = normalize_for_compare(s)
    t_norm = normalize_for_compare(t)
    if len(s_norm) != len(t_norm):
        return False
    return Counter(s_norm) == Counter(t_norm)


if __name__ == "__main__":
    # Built from explicit codepoint escapes so the composed/decomposed
    # distinction is unambiguous regardless of source-file encoding.
    precomposed = "caf" + "\u00e9"          # c a f e-acute (1 codepoint, U+00E9)
    decomposed = "caf" + "e" + "\u0301"     # c a f e + combining acute (U+0301)

    print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
    print("raw equal (no normalization)?", decomposed == precomposed)
    print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))

    reordered_precomposed = "\u00e9" + "fac"          # e-acute f a c (reordered anagram)
    strasse_lower = "stra" + "\u00df" + "e"           # stra-sharp_s-e

    tests = [
        ("listen", "silent", True),
        ("Listen", "Silent", True),
        (precomposed, decomposed + "x", False),
        (precomposed, reordered_precomposed, True),
        (decomposed, reordered_precomposed, True),
        ("STRASSE", strasse_lower, True),   # casefold('ss') == casefold('\u00df')
        ("ab", "abc", False),
    ]
    for a, b, expected in tests:
        result = is_anagram(a, b)
        print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")

    print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
    print("casefold(strasse_lower) =", strasse_lower.casefold())
    print("casefold('STRASSE') =", "STRASSE".casefold())

Output (actual run):

raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6  raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse

The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.

Trade-offs and pitfalls

• Comparing raw strings, or even lowercasing with .lower() instead of .casefold(), silently fails on real internationalized input like the ß/ss case above; .lower() alone leaves ß unchanged and would report STRASSE and straße as not anagrams, which is wrong under Unicode caseless matching rules.
• Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
• Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
• Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
• NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.