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
- The optimal strategy is to type some letters, then spend one keystroke on select, one on copy, and the rest on pasting.
- Let
dp[i]be the maximum number of letters afterikeystrokes. - If the last block starts after
jkeystrokes, the clipboard holdsdp[j]letters, and the remainingi - j - 1keystrokes (one select-copy pair plus pastes) multiply it byi - j - 1. - So
dp[i] = max(dp[i], dp[j] * (i - j - 1))for everyj <= 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 - jas the multiplier: one of the keystrokes is the copy, so onlyi - j - 1pastes 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.