The marquee swap

The marquee out front holds tonight's film in plastic letters. Tomorrow's film goes up at midnight, and the letter box in the office is locked.

The problem

A single-screen cinema spells its programme on a board of clip-in letters. Changing the board means taking every letter down and clipping the new title up from that same pile — no letter may be fetched from store, and no letter may be left over at the end. Spacing between words is done with blank slugs, of which there are always plenty, and the board carries one case only, so both titles reach you as lowercase letters with the spaces already stripped.

Given tonight's title and tomorrow's, decide whether the swap can be done from the letters on the board alone.

Input. tonight and tomorrow — two strings of lowercase letters.

Output. True if tomorrow's title uses exactly the letters of tonight's, each the same number of times; False otherwise.

Example.

tonight = "silence", tomorrow = "license"   ->  True

Both need one c, one i, one l, one n, one s and two e — the same pile, clipped up in a different order.

A second example, where the count is what decides it:

tonight = "matinee", tomorrow = "manatee"   ->  False

Seven letters each, but tomorrow wants a second a and has no slot for the i.

Constraints.

• 0 <= len(tonight), len(tomorrow) <= 10^5
• both strings contain only the characters a–z

Hints

Approach

Brute force

For each letter of tomorrow's title, scan tonight's for a match and cross it off. With titles of 10⁵ characters that is up to 10¹⁰ character comparisons, plus the cost of rebuilding the remaining pile after every removal.

The insight

Two titles are swappable exactly when their letter tallies agree, so one pass that adds tonight's letters and subtracts tomorrow's decides it — every entry back at zero means yes.

Order carries no information here, and a tally is what survives when order is discarded. It is a complete summary: two strings have the same tally if and only if each is a rearrangement of the other. Twenty-six counters hold it whatever the titles' length, so the whole check fits in fixed space.

Algorithm

1. If the lengths differ, answer False — a leftover letter is a leftover letter.
2. Make 26 counters, all zero.
3. Walk tonight, adding one to the counter for each letter.
4. Walk tomorrow, subtracting one from the counter for each letter.
5. Answer True if every counter is zero.

Complexity

Time O(n) — two passes over the titles and one over 26 counters. Space O(1) — the tally has 26 slots no matter how long the titles are.

Solution

"""The marquee swap — compare two titles by letter tally in one pass."""


def solve(tonight, tomorrow):
    if len(tonight) != len(tomorrow):
        return False
    tally = [0] * 26
    for ch in tonight:
        tally[ord(ch) - 97] += 1
    for ch in tomorrow:
        tally[ord(ch) - 97] -= 1
    # invariant: tally[i] is tonight's count of letter i minus tomorrow's,
    # so the swap works exactly when every entry is back at zero
    return all(count == 0 for count in tally)

TESTS = [
    (("silence", "license"), True),
    (("matinee", "manatee"), False),
    (("abbb", "aabb"), False),
    (("noon", "nono"), True),
    (("reel", "reels"), False),
    (("", ""), True),
    (("a", ""), False),
]

Pitfalls

• Comparing the sets of letters used accepts abbb for aabb: both use a and b, but the board would run out of b. Compare counts, not membership.
• Skipping the length check is safe only if you also verify no counter went negative and none is left positive; checking "nothing negative" alone accepts a shorter tomorrow and leaves letters on the board.
• Comparing sorted strings is correct but costs O(n log n) and allocates two copies; the tally does it in a single linear pass.

Variants

• One tray per formula — the same tally, used as a dictionary key to bin many strings rather than compare two.