Skip to main content
Talentd

4 Keys Keyboard - Solution & Explanation

MediumPremiumFree on FleetCodeMathDynamic Programming4 min readAsked at: Microsoft, Google
Practice this problem

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²).

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive ExplorationO(2^n)O(n)Conceptual understanding of all operation sequences
Dynamic ProgrammingO(n^2)O(n)Optimal solution for interview and production constraints

Video Solution

Leetcode 651. 4 Keys Keyboard (1d dp) • LetsCode • 857 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is 4 Keys Keyboard easy or hard?
LeetCode classifies 4 Keys Keyboard as Medium difficulty. The challenge is recognizing the optimal moment to switch from typing characters to performing copy–paste operations and expressing that decision with dynamic programming.
4 Keys Keyboard Python/Java solution
Implement a DP array where dp[i] represents the best result with i keystrokes. Initialize dp[i] = i (typing A each time), then test breakpoints j where you copy at j and paste afterward using dp[j] * (i - j - 1). The same logic works in Python, Java, C++, and Go.
How to solve 4 Keys Keyboard in O(n)?
The standard editorial solution uses O(n^2) dynamic programming. Some optimized observations limit the number of breakpoints you test (usually the last 3–5 positions), which can reduce constant factors, but the commonly accepted complexity remains O(n^2).
What is the best approach for 4 Keys Keyboard?
Dynamic programming is the most effective approach. Define dp[i] as the maximum number of 'A's you can produce with i keystrokes. For each i, try breaking at position j where you perform Ctrl-A and Ctrl-C, then paste multiple times. This evaluates all copy–paste strategies in O(n^2) time and O(n) space.
Is 4 Keys Keyboard asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies because it tests dynamic programming and reasoning about operation sequences. Similar optimization problems involving copy–paste or operation planning have been reported in Google and Amazon interview prep discussions.
What data structure is used in 4 Keys Keyboard?
A one-dimensional dynamic programming array is used. The array stores the maximum number of 'A's achievable for each number of keystrokes, allowing the algorithm to reuse previously computed optimal results.
What is the time complexity of 4 Keys Keyboard?
The optimal dynamic programming solution runs in O(n^2) time because for each keystroke count i you check all previous breakpoints j. Space complexity is O(n) for the DP array storing the best result for each number of keystrokes.

Ready to solve this problem?

Practice 4 Keys Keyboard with our built-in code editor and test cases.

Practice on FleetCode
Previous

2 Keys Keyboard