Valid Anagram

Binary Search

Best Time to Buy and Sell Stock

Check whether two lowercase strings contain identical character frequencies.

Return whether `t` is an anagram of `s`: both strings must contain the same lowercase letters with the same multiplicities, possibly in a different order.

**Pattern: Frequency counting with a balance map**
- Mental model: every character in `s` adds one credit, and every character in `t` spends one credit.
- Invariant: after processing matching positions from both strings, each map value is the net difference seen so far.
- Complexity: counting is O(n) time and O(k) space for `k` distinct characters; sorting is simpler but costs O(n log n).

**Input / output**
- Input: `s: string`, `t: string`
- Output: boolean

**Examples**
1. `s = "anagram", t = "nagaram"` returns `true`.
2. `s = "rat", t = "car"` returns `false`.

**Constraints**
- `0 <= s.length, t.length <= 100,000`
- Both strings contain lowercase English letters only

**Follow-up**
How would full Unicode support change the counting and normalization strategy?

- Two strings are anagrams only when they use the same characters with the same frequencies.
- Rearranging is allowed, but adding, removing, or changing a character is not.
- If the lengths differ, they cannot be anagrams.

Understand the Requirement

- Sorting both strings puts equal characters next to each other.
- If the sorted strings are equal, the original strings contain the same letters.
- This works, but sorting costs O(n log n) time.

Start with a Sorting Approach

- A faster approach is to count how many times each character appears.
- Increment counts for characters in `s`.
- Decrement counts for characters in `t`; every count should return to zero.

Use Character Counts Instead

- Length checking avoids unnecessary work.
- If one string has extra characters, no count-based comparison can succeed.
- After this guard, each index in `s` can be paired with the same index in `t` for counting.

Reject Different Lengths Early

Trace `s = "rat"`, `t = "car"` after the length check passes. Increment for the character from `s`; decrement for the character from `t`.

| index | from `s` | from `t` | counts after update |
|---:|---|---|---|
| 0 | `r` | `c` | `{r: 1, c: -1}` |
| 1 | `a` | `a` | `{r: 1, c: -1, a: 0}` |
| 2 | `t` | `r` | `{r: 0, c: -1, a: 0, t: 1}` |

The final map has nonzero counts for `c` and `t`, so the strings are not anagrams.

Dry run / state trace

- Skipping the length check and doing extra work for strings that cannot match.
- Comparing only sets of characters; `"aab"` and `"abb"` use the same set but are not anagrams.
- Forgetting to verify that every final count is zero after decrementing.
- Claiming sorting is optimal; it is acceptable, but counting improves time from O(n log n) to O(n).
- Follow-ups: how should the answer change for uppercase letters, spaces, accents, or Unicode normalization?

Recommended next problem in this pattern: **Two Sum**, which uses the same hash-map lookup idea for complements and indices.

Common mistakes & interviewer follow-ups

- The dictionary stores the frequency balance for each character.
- Any nonzero final count means one string used that character more often.
- Time complexity is O(n), and space complexity is O(k), where `k` is the number of distinct characters.