⚡Flashcard Drill➔
NeetCode #664LC-651Medium1-D Dynamic ProgrammingNC Algo100
← Back to All Problems

#664 · #651 · 4 Keys Keyboard(4 键键盘)

📌 Problem Statement & Constraints

Imagine a keyboard with four keys: A (print one letter A), Ctrl-A (select all), Ctrl-C (copy the selection), and Ctrl-V (paste the clipboard). You may press keys n times. Return the maximum number of letters A that can be printed. Constraints: 1 <= n <= 50.

💡 Core Algorithmic Approaches

  1. The optimal strategy is to type some letters, then spend one keystroke on select, one on copy, and the rest on pasting.
  2. Let dp[i] be the maximum number of letters after i keystrokes.
  3. If the last block starts after j keystrokes, the clipboard holds dp[j] letters, and the remaining i - j - 1 keystrokes (one select-copy pair plus pastes) multiply it by i - j - 1.
  4. So dp[i] = max(dp[i], dp[j] * (i - j - 1)) for every j <= i - 3, with the typing-only case as the baseline.

💻 Benchmark Python3 Implementation

class Solution:
    def maxA(self, n: int) -> int:
        dp = list(range(n + 1))        # typing A n times is the baseline
        for i in range(1, n + 1):
            for j in range(1, i - 2):  # 2 keys to select and copy, 1 to paste
                dp[i] = max(dp[i], dp[j] * (i - j - 1))
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): the nested loops over break points.
💾 Space Complexity
O(n): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming every keystroke is A: pasting after a copy multiplies the count, which is the entire point of the problem.
  • Using i - j as the multiplier: one of the keystrokes is the copy, so only i - j - 1 pastes remain.
  • Allowing j > i - 3: at least three keystrokes are needed for select, copy, and one paste.
  • Assuming a single copy cycle is optimal: the DP examines every break point, so multiple cycles are found automatically when they help.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems