Same Letter Bag
EasyTries & StringsFree
Problem
In a word game you may rearrange tiles but never add or remove one. Given two strings a and b, return true if b can be formed by rearranging all the letters of a.
Example 1
- Input:
- a = "listen", b = "silent"
- Output:
- true
Both contain e, i, l, n, s, t exactly once.
Example 2
- Input:
- a = "abc", b = "abd"
- Output:
- false
Constraints
- 0 ≤ a.length, b.length ≤ 5·10^4
- Strings are lowercase English letters.
Hint
Show the first hint
Order does not matter; what does?
Walkthrough
How to approach it
01Clarify before coding
- Are the lengths guaranteed equal? No; different lengths mean false immediately.
- Only lowercase letters? Yes, so a fixed array of 26 counters works.
- Is the empty string a rearrangement of the empty string? Yes.
02Brute force
Sort both strings and compare them.
Cost: O(n log n) time and O(n) memory for the sorted copies.
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.