Imagine you have a special keyboard with the following keys:
'A' on the screen.Given an integer n, return the maximum number of 'A' you can print on the screen with at most n presses on the keys.
Example 1:
Input: n = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing the following key sequence: A, A, A
Example 2:
Input: n = 7 Output: 9 Explanation: We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Constraints:
1 <= n <= 50Problem Overview: You have a keyboard with four operations: press A, Ctrl-A (select all), Ctrl-C (copy), and Ctrl-V (paste). Given n keystrokes, maximize the number of A characters that appear on the screen. The challenge is deciding when to stop typing A and start using copy–paste sequences to multiply what you already have.
Approach 1: Recursive Exploration (Exponential Time)
The brute force idea explores every possible sequence of operations. At each step you either type A or start a copy sequence (Ctrl-A, Ctrl-C, followed by multiple Ctrl-V). This forms a large decision tree where each state depends on the current screen count and remaining operations. Because the same states repeat many times, the recursion grows exponentially with roughly O(2^n) time and O(n) recursion space. This approach helps you understand the structure of the problem but quickly becomes infeasible for larger n.
Approach 2: Dynamic Programming (O(n²) time, O(n) space)
The key insight: an optimal solution eventually performs a copy sequence. That sequence always follows the pattern Ctrl-A → Ctrl-C → Ctrl-V.... If you stop typing at step j, copy everything, and paste for the remaining steps, you multiply the characters produced by step j. Define dp[i] as the maximum number of As obtainable with i keystrokes. The baseline is simply typing: dp[i] = i.
For every i, try a breakpoint j where you perform Ctrl-A and Ctrl-C. After those two operations, the remaining i - j - 2 steps are pastes. Each paste adds the copied content, so the total becomes dp[j] * (i - j - 1). Iterate j from 1 to i-3 and take the maximum. This captures every valid copy-paste strategy while avoiding redundant computation. The nested loop gives O(n²) time and the DP array requires O(n) space.
This problem is a classic example of dynamic programming where each state depends on optimal solutions to smaller states. It also involves reasoning about operation counts and multiplication patterns, which ties into math optimization ideas.
Recommended for interviews: The dynamic programming approach. Interviewers expect you to recognize the copy–paste block pattern and model it with dp[i]. Mentioning the brute force recursion first shows you understand the search space, but transitioning to the DP optimization demonstrates the algorithmic insight needed to reduce exponential exploration to O(n²).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Exploration | O(2^n) | O(n) | Conceptual understanding of all operation sequences |
| Dynamic Programming | O(n^2) | O(n) | Optimal solution for interview and production constraints |
Leetcode 651. 4 Keys Keyboard (1d dp) • LetsCode • 786 views views
Watch 5 more video solutions →Practice 4 Keys Keyboard with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor