Same Letter Tiles

Easyhash mapAlso known as Valid Anagram

You are playing a word game with letter tiles. You lay down listen. Your friend scoops up your six tiles, shuffles them, and lays down silent. Legal move: same tiles, new order.

Next round she tries to turn your teeth into teethe. That needs a sixth tile she does not have. You want a quick way to check any claimed rearrangement.

Your task

Write sameTiles(word, rearranged). Return true if rearranged uses exactly the same letters as word, each letter the same number of times, in any order. Otherwise return false.

Both strings contain only lowercase letters a to z. Two empty strings count as the same tiles.

sameTiles(word: string, rearranged: string) → bool

Examples

Example 1

Input

word = "listen"
rearranged = "silent"

Output

true

Why

Both have one each of e, i, l, n, s, t. The order is different, the tiles are the same.

Example 2

Input

word = "teeth"
rearranged = "teethe"

Output

false

Why

The lengths differ, 5 against 6, so at least one tile is missing. No need to look further.

Example 3

Input

word = "brag"
rearranged = "garb"

Output

true

Why

b, r, a, g in both. Shuffled, but nothing added and nothing left over.

Constraints

0 ≤ word.length, rearranged.length ≤ 50,000
Only lowercase English letters.

Start with brute force

For each letter of word, search rearranged for a matching unused tile and cross it off. If you ever fail to find one, the answer is no.

Each search scans the second word, so this is O(n²). With 50,000 letters that is over a billion steps. Sorting both words and comparing them works in O(n log n), which is fine, but counting is simpler and faster.

Hints

0 of 4 shown

Hint 1
Compare aab and abb. They use the same set of letters. Why are they still not the same tiles?
Hint 2
What matters is how many of each letter there are. Two words are the same tiles exactly when every letter has the same count in both.
Hint 3
Count the letters of the first word. How could the second word "use up" those counts, and what would you look for at the end?
Hint 4
If the lengths differ, return false. Otherwise build a map letter → count from word, then walk rearranged and subtract one per letter. If any count drops below zero, a tile is missing: return false. If you finish, return true.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Order does not matter, only how many of each letter there are. So count the tiles of the first word, then let the second word spend them.

Trace teeth against tethe (same length, 5):

Count teeth: t → 2, e → 2, h → 1.
Spend t: t → 1. Spend e: e → 1. Spend t: t → 0.
Spend h: h → 0. Spend e: e → 0.
No count went below zero, so every tile was matched. Return true.

Why is it enough to check for negatives? The lengths are equal. If some letter were short, another letter would have to be over-used to make up the length, and that one would go negative.

Reference solution

function sameTiles(word, rearranged) {
  if (word.length !== rearranged.length) return false;
  const count = new Map(); // letter -> tiles still unused
  for (const ch of word) count.set(ch, (count.get(ch) || 0) + 1);
  for (const ch of rearranged) {
    const left = (count.get(ch) || 0) - 1;
    if (left < 0) return false; // no tile left for this letter
    count.set(ch, left);
  }
  return true;
}

def same_tiles(word, rearranged):
    if len(word) != len(rearranged):
        return False
    count = {}  # letter -> tiles still unused
    for ch in word:
        count[ch] = count.get(ch, 0) + 1
    for ch in rearranged:
        left = count.get(ch, 0) - 1
        if left < 0:  # no tile left for this letter
            return False
        count[ch] = left
    return True

TimeO(n)Two passes over strings of length n, with O(1) map work per letter.

SpaceO(1)The map holds at most 26 letters, however long the words are.

Learn the idea: Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code