# LeetCode 383: Ransom Note

## Problem Restatement

We are given two strings:

```python
ransomNote
magazine
```

We need to decide whether `ransomNote` can be built using letters from `magazine`.

Each letter from `magazine` can be used at most once.

So we need enough copies of every character required by `ransomNote`.

For example, if `ransomNote = "aa"` and `magazine = "ab"`, the answer is `False`, because `magazine` has only one `a`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings: `ransomNote` and `magazine` |
| Output | `True` if `ransomNote` can be built, otherwise `False` |
| Constraint | `1 <= ransomNote.length, magazine.length <= 10^5` |
| Constraint | Both strings contain only lowercase English letters |

Example function shape:

```python
def canConstruct(ransomNote: str, magazine: str) -> bool:
    ...
```

## Examples

Example 1:

```python
ransomNote = "a"
magazine = "b"
```

The note needs one `a`.

The magazine has no `a`.

So the answer is:

```python
False
```

Example 2:

```python
ransomNote = "aa"
magazine = "ab"
```

The note needs two `a` letters.

The magazine has only one `a`.

So the answer is:

```python
False
```

Example 3:

```python
ransomNote = "aa"
magazine = "aab"
```

The note needs two `a` letters.

The magazine has two `a` letters.

So the answer is:

```python
True
```

## First Thought: Search and Remove

A direct idea is to process each character in `ransomNote`.

For each character, search for it inside `magazine`.

If found, remove one copy from `magazine`.

If not found, return `False`.

For example:

```python
ransomNote = "aa"
magazine = "aab"
```

Use the first `a`, leaving:

```python
"ab"
```

Use the second `a`, leaving:

```python
"b"
```

Now the note can be constructed.

This works logically, but strings are immutable in Python. Removing a character creates a new string, which costs time. Repeated searching and removing can become too slow for input length up to `10^5`.

## Key Insight

We only care about character counts.

The order of letters in `magazine` does not matter.

We need to know whether `magazine` contains at least as many copies of each character as `ransomNote`.

So we count the letters in `magazine`, then consume them while scanning `ransomNote`.

## Algorithm

Create an array of size `26`.

Each index represents one lowercase English letter.

```python
count[0] -> number of 'a'
count[1] -> number of 'b'
count[2] -> number of 'c'
```

First, scan `magazine` and count every letter.

Then scan `ransomNote`.

For each character:

1. Convert it to an index from `0` to `25`.
2. Decrease its count.
3. If the count becomes negative, return `False`.

If the whole `ransomNote` is processed successfully, return `True`.

## Correctness

The array `count` stores how many unused copies of each magazine letter remain.

After scanning `magazine`, `count` correctly records the available supply of every letter.

When processing `ransomNote`, each character uses one available copy of that same character. Decrementing the corresponding count models this use.

If a count becomes negative, then the note requires more copies of that character than the magazine provides. In that case, construction is impossible, so returning `False` is correct.

If no count becomes negative, every required letter was matched with a distinct magazine letter. Since each decrement consumes one copy, no magazine letter is reused.

Therefore returning `True` is correct.

## Complexity

Let `n = len(ransomNote)` and `m = len(magazine)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | We scan both strings once |
| Space | `O(1)` | The count array always has size `26` |

## Implementation

```python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26

        for ch in magazine:
            idx = ord(ch) - ord("a")
            count[idx] += 1

        for ch in ransomNote:
            idx = ord(ch) - ord("a")
            count[idx] -= 1

            if count[idx] < 0:
                return False

        return True
```

## Code Explanation

We create a fixed-size frequency table:

```python
count = [0] * 26
```

Then we count letters from `magazine`:

```python
for ch in magazine:
    idx = ord(ch) - ord("a")
    count[idx] += 1
```

The expression:

```python
ord(ch) - ord("a")
```

maps:

```text
'a' -> 0
'b' -> 1
'c' -> 2
...
'z' -> 25
```

Then we consume letters required by `ransomNote`:

```python
for ch in ransomNote:
    idx = ord(ch) - ord("a")
    count[idx] -= 1
```

If the count becomes negative:

```python
if count[idx] < 0:
    return False
```

then the magazine does not contain enough of that character.

If the loop finishes, all letters were available:

```python
return True
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.canConstruct("a", "b") is False
    assert s.canConstruct("aa", "ab") is False
    assert s.canConstruct("aa", "aab") is True
    assert s.canConstruct("abc", "cba") is True
    assert s.canConstruct("aabbcc", "abcabc") is True
    assert s.canConstruct("aabbcc", "abcab") is False
    assert s.canConstruct("zz", "z") is False

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `"a"`, `"b"` | Missing required letter |
| `"aa"`, `"ab"` | Not enough copies |
| `"aa"`, `"aab"` | Enough repeated letters |
| `"abc"`, `"cba"` | Order does not matter |
| `"aabbcc"`, `"abcabc"` | Exact frequency match |
| `"aabbcc"`, `"abcab"` | One character count is too small |
| `"zz"`, `"z"` | Checks repeated high-index character |