Same Letters, New Order
EasyArrays & HashingFree
Problem
A word-game app accepts a guess only if it uses exactly the letters of the puzzle word: the same letters, each the same number of times, in any order.
Given two strings a and b, return true if b is a rearrangement of a, and false otherwise.
Example 1
- Input:
- a = "listen", b = "silent"
- Output:
- true
Both contain one each of e, i, l, n, s, t.
Example 2
- Input:
- a = "rat", b = "car"
- Output:
- false
b has a 'c' that a lacks, and lacks a 't'.
Constraints
- 0 ≤ a.length, b.length ≤ 5·10^4
- a and b contain only lowercase English letters.
Hint
Show the first hint
Order does not matter, only how many times each letter occurs.
Walkthrough
How to approach it
01Clarify before coding
- Are the letters case-sensitive or limited to lowercase? Only lowercase a–z here, so 26 counters suffice.
- Is an empty string a rearrangement of another empty string? Yes: zero letters each.
- What about different lengths? They can never match; that is a free early exit.
02Brute force
Sort both strings and compare them character by character.
Cost: O(n log n) time and O(n) space for the sorted copies; correct, but the sort does more work than the question needs.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.