4 Keys Keyboard

4 Keys Keyboard

What is this problem about?

The 4 Keys Keyboard coding problem describes a specialized keyboard with four keys:

1. A: Print one 'A' on the screen.
2. Ctrl-A: Select the entire screen.
3. Ctrl-C: Copy the selection to the buffer.
4. Ctrl-V: Paste the buffer to the screen. Given $N$ keystrokes, what is the maximum number of 'A's you can display?

Why is this asked in interviews?

This problem is a classic at Microsoft and Google because it tests Dynamic Programming (DP) skills. It requires the candidate to identify the "optimal substructure"—recognizing that the best way to get a large number of 'A's is to print some, then repeatedly select, copy, and paste.

Algorithmic pattern used

This is a Dynamic Programming interview pattern. You build a dp table where dp[i] represents the maximum 'A's possible with i keystrokes. To calculate dp[i], you either:

• Press 'A' (which is dp[i-1] + 1).
• Look back at some j where you performed a "Select + Copy" and then performed "Paste" $i-j-1$ times.

Example explanation

For $N = 7$:

• Keys 1, 2, 3: "A", "A", "A" (Total 3)
• Key 4: Ctrl-A (Select)
• Key 5: Ctrl-C (Copy "AAA")
• Key 6: Ctrl-V (Paste $\rightarrow$ "AAAAAA")
• Key 7: Ctrl-V (Paste $\rightarrow$ "AAAAAAAAA") Total: 9 'A's. The DP logic explores whether it was better to copy at step 3, 4, or 5 to maximize the final output.

Common mistakes candidates make

• Missing the "Select-Copy" cost: Forgetting that Ctrl-A and Ctrl-C take two separate keystrokes before you can start pasting.
• Over-counting: Thinking you can Ctrl-V without a Ctrl-C, or Ctrl-C without a Ctrl-A.
• Suboptimal DP: Not checking enough "previous" states. You need to check multiple potential "copy" points to find the maximum.

Interview preparation tip

In DP problems involving sequences of actions, try to find the "jump" point. Here, the jump is the Copy-Paste sequence. Visualize how the buffer changes to understand the state transitions.