LeetCode 651 - 4 Keys Keyboard

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem gives us a keyboard with four operations:

Press A, which inserts one character 'A'
Press Ctrl-A, which selects everything currently on the screen
Press Ctrl-C, which copies the selected text into a clipboard buffer
Press Ctrl-V, which pastes the clipboard contents onto the screen

We are given an integer n, representing the maximum number of key presses we are allowed to make. The goal is to determine the maximum number of 'A' characters that can appear on the screen after at most n operations.

At first glance, repeatedly pressing A seems straightforward. If n = 5, we could simply press A five times and end up with five characters. However, the copy and paste operations introduce the possibility of exponential growth. For example, after building a reasonable amount of text, we can copy the entire screen and paste it multiple times, multiplying the number of characters much faster than typing individually.

The input consists of a single integer:

n, the number of allowed key presses

The output is:

The maximum number of 'A' characters achievable within those key presses

The constraints are small:

1 <= n <= 50

This immediately suggests that dynamic programming is feasible. Since the input size is tiny, even an O(n^2) or O(n^3) solution would run comfortably within limits.

Several edge cases are important:

Very small values such as n = 1, n = 2, or n = 3, where copy and paste operations are useless because they consume too many presses.
Situations where copying too early reduces total output because the clipboard operation itself costs two key presses (Ctrl-A and Ctrl-C).
Ensuring that paste operations only happen after a valid copy sequence.

The problem guarantees that n is always at least 1, so we never need to handle invalid or empty input.

Approaches

Brute Force Approach

A brute force solution would try every possible sequence of operations up to length n. At each step, we could choose among four actions:

Type A
Select all
Copy
Paste

To make this work, we would need to track:

The current screen content length
The clipboard size
Whether text is selected

The recursion tree grows extremely quickly because each key press branches into multiple possible actions. Even with pruning, the number of states becomes enormous.

This approach is correct because it explores every valid sequence of operations and therefore cannot miss the optimal answer. However, it is computationally infeasible due to exponential growth.

Key Insight

The important observation is that the optimal strategy always looks like this:

Type some number of As
Perform:

Ctrl-A
Ctrl-C

Paste multiple times

The moment we decide to start copying, we should paste repeatedly afterward. Interleaving additional typing operations is never better than using the clipboard efficiently.

This leads naturally to dynamic programming.

Let dp[i] represent the maximum number of 'A' characters obtainable using exactly i key presses.

For every i, we have two possibilities:

Press A one more time:
dp[i] = dp[i - 1] + 1
Use a copy-paste sequence:
Suppose we stop at some earlier point j
At step j, we already have dp[j] characters
We spend two operations on:
Ctrl-A
Ctrl-C
The remaining operations are all pastes
If we paste k times, the screen becomes dp[j] * (k + 1)

This transforms the exponential brute force into a polynomial-time DP solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(n)	Explores every possible operation sequence
Optimal Dynamic Programming	O(n²)	O(n)	Builds best answer for each number of key presses

Algorithm Walkthrough

Create a DP array where dp[i] stores the maximum number of 'A' characters achievable using exactly i key presses.
Initialize the base cases. For small values of i, the best strategy is simply pressing A repeatedly. Therefore:

dp[1] = 1
dp[2] = 2
dp[3] = 3

For every number of key presses from 1 to n, first assume we simply type another A.

This gives:

dp[i] = dp[i - 1] + 1

Next, consider every possible earlier breakpoint j where we stop typing and begin a copy-paste sequence.

At position j:

We already have dp[j] characters
We spend:
one operation for Ctrl-A
one operation for Ctrl-C
Remaining operations are pastes

The number of paste operations is:

i - j - 2

Every paste adds another dp[j] characters. Since the original screen already contains dp[j], the final total becomes:

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

Update the maximum:

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

Continue until all values up to n are computed.
Return dp[n].

Why it works

The DP works because every optimal solution can be decomposed into smaller optimal solutions. Before the first copy operation, we must already have built the best possible screen for that number of key presses. After copying, every remaining operation should be a paste because pasting multiplies existing work more efficiently than typing individual characters. By evaluating every possible breakpoint j, the algorithm guarantees that the globally optimal strategy is considered.

Python Solution

class Solution:
    def maxA(self, n: int) -> int:
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            # Option 1: press 'A'
            dp[i] = dp[i - 1] + 1

            # Option 2: use copy-paste sequence
            for j in range(1, i - 2):
                current = dp[j] * (i - j - 1)
                dp[i] = max(dp[i], current)

        return dp[n]

The implementation directly follows the recurrence relation developed earlier.

The DP array stores the best possible answer for every number of key presses from 0 to n.

For each position i, the algorithm first assumes we simply press A, which gives dp[i - 1] + 1.

Then the inner loop considers every earlier breakpoint j. At that point, we already have dp[j] characters on screen. We spend two operations on selecting and copying, and the remaining operations become paste operations.

The formula:

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

represents the total number of characters after repeated pasting.

The maximum value across all possibilities becomes dp[i].

Because n is at most 50, the quadratic complexity is extremely efficient.

Go Solution

func maxA(n int) int {
	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		// Option 1: press 'A'
		dp[i] = dp[i-1] + 1

		// Option 2: copy-paste sequence
		for j := 1; j <= i-3; j++ {
			current := dp[j] * (i - j - 1)

			if current > dp[i] {
				dp[i] = current
			}
		}
	}

	return dp[n]
}

The Go implementation mirrors the Python logic almost exactly.

Slices are used instead of Python lists. Since Go does not provide a built-in max function for integers, we use a simple conditional comparison to update the DP value.

Integer overflow is not a concern because the maximum answer for n <= 50 easily fits within Go's standard integer range.

Worked Examples

Example 1

Input:

n = 3

Since there are too few operations to benefit from copying, the optimal strategy is simply typing A three times.

i	Best Action	dp[i]
1	A	1
2	A, A	2
3	A, A, A	3

Final answer:

Example 2

Input:

n = 7

We compute the DP table step by step.

i	Best Computation	dp[i]
1	Type A	1
2	Type A	2
3	Type A	3
4	Type A	4
5	Type A	5
6	Either type or copy strategy	6
7	Copy at j=3, then paste twice	9

For i = 7:

At j = 3, we already have 3 A's
Use:
Ctrl-A
Ctrl-C
Remaining operations:
Ctrl-V
Ctrl-V

Total:

3 * 3 = 9

Sequence:

A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Nested loops over all pairs `(i, j)`
Space	O(n)	DP array of size `n + 1`

The outer loop iterates from 1 to n, and the inner loop checks every earlier breakpoint. This produces quadratic time complexity.

The space complexity is linear because we only store one DP array.

Test Cases

solution = Solution()

assert solution.maxA(1) == 1  # minimum input
assert solution.maxA(2) == 2  # simple typing only
assert solution.maxA(3) == 3  # copying still not useful
assert solution.maxA(4) == 4  # direct typing remains optimal
assert solution.maxA(5) == 5  # no advantage yet from copy-paste
assert solution.maxA(6) == 6  # tie between strategies
assert solution.maxA(7) == 9  # first strong copy-paste benefit
assert solution.maxA(8) == 12  # multiple pastes improve output
assert solution.maxA(9) == 16  # optimal multiplication pattern
assert solution.maxA(10) == 20  # larger DP transition
assert solution.maxA(15) == 81  # stress medium-sized value
assert solution.maxA(20) == 324  # larger multiplication chain
assert solution.maxA(50) > 0  # upper constraint boundary

Test	Why
`n = 1`	Verifies minimum boundary
`n = 2`	Confirms simple typing behavior
`n = 3`	Ensures no premature copy usage
`n = 4`	Validates direct typing strategy
`n = 5`	Confirms copy is still inefficient
`n = 6`	Tests transition point
`n = 7`	First major copy-paste optimization
`n = 8`	Verifies repeated paste logic
`n = 9`	Checks multiplicative growth
`n = 10`	Tests larger DP combinations
`n = 15`	Medium-sized stress test
`n = 20`	Validates scaling behavior
`n = 50`	Confirms upper constraint handling

Edge Cases

One important edge case is very small values of n, especially n <= 3. In these cases, any attempt to use Ctrl-A and Ctrl-C wastes too many operations. A naive implementation might incorrectly force a copy-paste strategy too early. The DP formulation naturally handles this because simply typing A always remains one of the candidate transitions.

Another critical edge case occurs when the optimal breakpoint is not immediately before the final operations. For example, in n = 9, the best strategy is not to copy as late as possible. A greedy approach that always copies near the end can fail badly. The DP solution avoids this issue by evaluating every possible breakpoint j.

A third edge case involves ensuring enough operations remain after copying. Performing Ctrl-A and Ctrl-C without at least one paste is useless. Incorrect loop bounds can accidentally allow invalid states. The implementation prevents this by only considering j values where at least three operations remain: one for select, one for copy, and at least one for paste.