# LeetCode 651: 4 Keys Keyboard

## Problem Restatement

We have a special keyboard with four operations:

| Key | Operation |
|---|---|
| `A` | Print one `A` on the screen |
| `Ctrl-A` | Select all text on the screen |
| `Ctrl-C` | Copy the selected text into a buffer |
| `Ctrl-V` | Paste the buffer after the current text |

Given an integer `n`, we can press keys at most `n` times.

Return the maximum number of `A` characters we can print on the screen.

The problem is asking for the best sequence of operations, not the sequence itself.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The maximum number of `A` characters possible |
| Constraint | We may use at most `n` key presses |
| Operation limit | Only `A`, `Ctrl-A`, `Ctrl-C`, and `Ctrl-V` are allowed |

Example function shape:

```python
def maxA(n: int) -> int:
    ...
```

## Examples

For `n = 3`, the best choice is to press `A` three times:

```text
A, A, A
```

The screen has:

```text
AAA
```

So the answer is `3`.

For `n = 7`, one optimal sequence is:

```text
A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V
```

After the first three operations, the screen has `AAA`.

Then we copy all three `A` characters.

Each paste adds three more `A` characters.

After two pastes, the screen has:

```text
AAAAAAAAA
```

So the answer is `9`.

## First Thought: Brute Force

A brute force solution would try every possible sequence of `n` key presses.

At every step, we have up to four choices:

```text
A
Ctrl-A
Ctrl-C
Ctrl-V
```

So the number of sequences grows roughly like:

```text
4^n
```

This is too large.

Many sequences are also useless. For example, pressing `Ctrl-C` before selecting anything does not help. Pressing `Ctrl-V` before copying anything does not help either.

We need to reason about the structure of an optimal sequence.

## Key Insight

There are two useful ways to finish a sequence.

The first way is simple: press `A`.

If we only press `A`, then after `i` key presses we get `i` characters.

The second way is copy and paste.

Any useful copy-paste block has this shape:

```text
Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, ...
```

This means we first build some number of `A` characters, select all of them, copy them, and then paste several times.

Suppose we already have the best result after `j` key presses.

Then we spend:

```text
Ctrl-A
Ctrl-C
```

That costs two more key presses.

Every remaining key press can be `Ctrl-V`.

If the total number of key presses is `i`, then the number of paste operations is:

```text
i - j - 2
```

The final screen contains the original text plus each pasted copy.

So the multiplier is:

```text
1 + (i - j - 2) = i - j - 1
```

Therefore, one candidate answer is:

```text
dp[j] * (i - j - 1)
```

## Dynamic Programming Definition

Let:

```python
dp[i]
```

mean:

```text
the maximum number of A characters we can print using exactly i key presses
```

The base idea is:

```python
dp[i] = i
```

because we can always press `A` exactly `i` times.

Then we try every possible earlier point `j` where we stop building text normally and start a copy-paste block.

## Algorithm

Initialize `dp` so that:

```python
dp[i] = i
```

This represents pressing `A` every time.

Then for each total number of key presses `i`:

1. Try every breakpoint `j`.
2. Treat `dp[j]` as the number of `A` characters already on the screen.
3. Use the remaining operations for `Ctrl-A`, `Ctrl-C`, and one or more `Ctrl-V`.
4. Update `dp[i]` with the best result.

The transition is:

```python
dp[i] = max(dp[i], dp[j] * (i - j - 1))
```

Here:

| Part | Meaning |
|---|---|
| `dp[j]` | Best number of `A`s after `j` key presses |
| `Ctrl-A`, `Ctrl-C` | Two required operations |
| `i - j - 2` | Number of paste operations |
| `i - j - 1` | Total multiplier after keeping the original plus pastes |

## Correctness

The dynamic programming state `dp[i]` stores the best possible result after `i` key presses.

For each `i`, there are two cases.

First, the optimal sequence may end by typing `A` repeatedly. This case is covered by the initialization `dp[i] = i`.

Second, the optimal sequence may end with one or more paste operations. In that case, before the final paste block begins, there must be some earlier key press count `j` where the screen already contains some text. The sequence then performs `Ctrl-A`, `Ctrl-C`, and several `Ctrl-V` operations.

The best possible amount of text before that block is `dp[j]`. The copy operation copies all of that text. Each paste adds another copy of the same text. With `i - j - 2` paste operations, the final multiplier is `i - j - 1`.

The algorithm checks every valid breakpoint `j`, so it checks every possible final copy-paste block. Since every optimal solution either uses only direct typing or has some final copy-paste block, the algorithm finds the optimal value.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | For each `i`, we try possible breakpoints `j` |
| Space | `O(n)` | We store one DP value for each key count |

## Implementation

```python
class Solution:
    def maxA(self, n: int) -> int:
        dp = list(range(n + 1))

        for i in range(1, n + 1):
            for j in range(1, i - 2):
                dp[i] = max(dp[i], dp[j] * (i - j - 1))

        return dp[n]
```

## Code Explanation

We start with:

```python
dp = list(range(n + 1))
```

This means:

```text
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
...
```

This represents the strategy of pressing `A` every time.

Then we compute every `dp[i]`.

```python
for i in range(1, n + 1):
```

For each total number of key presses, we try all possible places where the final copy-paste block could begin.

```python
for j in range(1, i - 2):
```

The value `j` means we already used `j` key presses to build some text.

Then we spend two operations:

```text
Ctrl-A, Ctrl-C
```

The rest are paste operations.

```python
dp[i] = max(dp[i], dp[j] * (i - j - 1))
```

This chooses the better result between the current best and the result created by copying `dp[j]` and pasting it repeatedly.

Finally:

```python
return dp[n]
```

returns the maximum number of `A` characters possible with `n` key presses.

## Testing

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

    assert s.maxA(1) == 1
    assert s.maxA(2) == 2
    assert s.maxA(3) == 3
    assert s.maxA(4) == 4
    assert s.maxA(5) == 5
    assert s.maxA(6) == 6
    assert s.maxA(7) == 9
    assert s.maxA(8) == 12
    assert s.maxA(9) == 16
    assert s.maxA(10) == 20

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Smallest useful input |
| `n = 2`, `3`, `4`, `5`, `6` | Direct typing is still optimal |
| `n = 7` | First case where copy-paste beats direct typing |
| `n = 8` | Confirms multiple paste operations |
| `n = 9` | Confirms a larger multiplier |
| `n = 10` | Checks a later DP state |