Leetcode 651. 4 Keys Keyboard (1d dp)
4 Keys Keyboard - Video Solution
Watch 5 video solutions for 4 Keys Keyboard, a medium level problem involving Math, Dynamic Programming. This walkthrough by LetsCode has 857 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Imagine you have a special keyboard with the following keys:
- A: Print one
'A'on the screen. - Ctrl-A: Select the whole screen.
- Ctrl-C: Copy selection to buffer.
- Ctrl-V: Print buffer on screen appending it after what has already been printed.
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 <= 50
Approach Overview
Problem 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²).
Complexity Analysis
| 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 |