LeetCode 651: 4 Keys Keyboard

Problem Restatement

We have a special keyboard with four operations:

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

Example function shape:

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

Examples

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

A, A, A

The screen has:

AAA

So the answer is 3.

For n = 7, one optimal sequence is:

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:

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:

A
Ctrl-A
Ctrl-C
Ctrl-V

So the number of sequences grows roughly like:

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:

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:

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:

i - j - 2

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

So the multiplier is:

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

Therefore, one candidate answer is:

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

Dynamic Programming Definition

Let:

dp[i]

mean:

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

The base idea is:

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:

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:

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

Here:

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

Implementation

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:

dp = list(range(n + 1))

This means:

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].

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.

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:

Ctrl-A, Ctrl-C

The rest are paste operations.

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:

return dp[n]

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

Testing

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: