4 Keys Keyboard

How it works

With n key presses, we want to maximize the number of 'A's on screen. At any point, we can either type 'A' or use Ctrl-A, Ctrl-C, then Ctrl-V to copy and paste. The key observation is that after pressing 'A' some number of times, it becomes more efficient to copy what we have and paste it multiple times. For a given number of 'A's, using Ctrl-A + Ctrl-C + k pastes multiplies the count by k + 1 (original + k copies). We use dynamic programming where dp[i] represents the maximum 'A's achievable with exactly i key presses.

Steps

1. Initialize dp array where dp[i] = i (worst case: just pressing 'A' each time).
2. For each position i from 0 to n - 3 (we need at least 3 keys for Ctrl-A, Ctrl-C, Ctrl-V):
   • Try different numbers of pastes from position i + 3 to min(n, i + 6).
   • For each j in this range, dp[j] = max(dp[j], (j - i - 1) * dp[i]).
   • The multiplier (j - i - 1) accounts for the original plus j - i - 2 paste operations (after 2 keys for Ctrl-A and Ctrl-C).
3. Return dp[n].

Complexity

• Time complexity: O(n)

• Space complexity: O(n)

Where n is the maximum number of key presses allowed.

Things to watch for

Miscounting the Copy-Paste Cost

A complete copy-paste sequence requires 3 keys minimum: Ctrl-A, Ctrl-C, and one Ctrl-V. Each additional paste is just 1 more key. A common mistake is forgetting that the first paste after copying costs 3 total operations, not 2.

Ignoring Small n Base Cases

For small values of n (typically n <= 6), just pressing 'A' repeatedly is optimal or nearly optimal. Trying to apply the copy-paste strategy too early wastes keystrokes on the copy operation when simply typing would yield more characters.

Wrong Multiplier Calculation

When pasting k times after copying, the total becomes (k+1) * original (original plus k copies). A common error is calculating the multiplier as just k instead of k+1, or miscounting how many paste operations fit in the remaining keystrokes.

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

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

        return dp[n]

class Solution {
public:
    int maxA(int n) {
        vector<int> dp(n + 1);
        iota(dp.begin(), dp.end(), 0);
        
        for (int i = 0; i <= n - 3; i++) {
            for (int j = i + 3; j <= min(n, i + 6); j++) {
                dp[j] = max(dp[j], (j - i - 1) * dp[i]);
            }
        }

        return dp[n];
    }
};