Maximum A's with Four Keys: DP Solution for Placement Rounds

The four-key keyboard problem asks how many A’s you can print with exactly N keystrokes, using only A, Ctrl+A, Ctrl+C, and Ctrl+V. Pressing A every time is not optimal past N = 6.

The Four-Key Setup

The keyboard supports exactly four operations:

• A — types one A onto the screen.
• Ctrl+A — selects all A’s currently visible on screen.
• Ctrl+C — copies the selection to clipboard; screen content stays unchanged.
• Ctrl+V — pastes the clipboard contents, appending them to what’s already on screen.

The task: with exactly N keystrokes available, find the maximum number of A’s you can produce.

Two constraints matter. Each of the four keys costs exactly one keystroke. Ctrl+A is not free. Pasting also requires a prior select-and-copy sequence; pasting from an empty clipboard adds nothing.

This type of problem appears in campus placement evaluation tests and algorithmic coding rounds because it distinguishes students who reach for a pattern-match (greedy) from those who structure a correct sub-problem decomposition (dynamic programming).

Why Greedy Fails

A greedy approach says: once you have some A’s worth copying, copy and paste for as many remaining keystrokes as possible.

Try N = 7 with greedy, copying after just 2 A’s:

• Keystrokes 1-2: A, A — 2 A’s on screen
• Keystroke 3: Ctrl+A; Keystroke 4: Ctrl+C — clipboard loaded
• Keystrokes 5, 6, 7: three Ctrl+V pastes — 2 + 2 + 2 + 2 = 8 A’s

The correct answer is 9. Greedy leaves one A on the table by copying too early.

Building 3 A’s first (three keystrokes) and then using the remaining four keystrokes for Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V gives 3 + 3 + 3 = 9 A’s. The decision of when to start copying depends on how many keystrokes remain, which a local greedy rule cannot evaluate.

Dynamic programming handles this by storing the optimal answer for every keystroke count from 1 to N, then building upward. Sub-problems overlap: the best result for N = 11 directly reuses the already-computed result for N = 7.

The DP Recurrence

Every optimal N-keystroke sequence ends with a single copy-paste block. Call the block size j keystrokes, where j = 1 Ctrl+A + 1 Ctrl+C + (j minus 2) Ctrl+V presses. The minimum block size is j = 3. The remaining N minus j keystrokes were spent building some count of A’s: a sub-problem the DP has already solved.

How many A’s does the block produce from a starting count of dp[N-j]?

• Ctrl+A selects all dp[N-j] A’s; Ctrl+C loads them to clipboard.
• The first Ctrl+V appends dp[N-j] more — screen total becomes 2 x dp[N-j].
• Each additional Ctrl+V appends dp[N-j] more.
• After (j minus 2) total pastes: dp[N-j] + (j-2) x dp[N-j] = dp[N-j] x (j-1).

The recurrence, also detailed on GeeksForGeeks:

dp[N] = max over j from 3 to N-1 of (dp[N-j] x (j-1))

For N from 1 to 6, no copy-paste block beats pressing A every time, so dp[N] = N for those values.

Why the multiplier is (j-1) and not j

With j keystrokes used for Ctrl+A, Ctrl+C, and k pastes, k equals j minus 2 and the total multiplier is k + 1 = j minus 1. For j = 3 (one paste), the multiplier is 2: you double the A count. For j = 4 (two pastes), the multiplier is 3: you triple it. The multiplier grows with each additional paste, but each additional paste also costs a keystroke that could have built more A’s first, which is why the recurrence takes the maximum across all valid j values.

Verified Answer Table: N = 1 to 12

Derived independently from the recurrence above:

N	Max A’s	Optimal strategy
1	1	A
2	2	A, A
3	3	A, A, A
4	4	A, A, A, A
5	5	A x5
6	6	A x6 (copy-paste ties at 6, not yet an improvement)
7	9	A x3, then CtrlA CtrlC CtrlV CtrlV (3 x 3)
8	12	A x4, then CtrlA CtrlC CtrlV CtrlV (4 x 3)
9	16	A x4, then CtrlA CtrlC CtrlV CtrlV CtrlV (4 x 4)
10	20	A x5, then CtrlA CtrlC CtrlV CtrlV CtrlV (5 x 4)
11	27	9 A’s in 7 strokes, then CtrlA CtrlC CtrlV CtrlV (9 x 3)
12	36	12 A’s in 8 strokes, then CtrlA CtrlC CtrlV CtrlV (12 x 3)

N = 7 is the threshold: the first value where a copy-paste block outperforms typing A every time.

Traced Examples

N = 7

• Keystroke 1: A — 1 A on screen
• Keystroke 2: A — 2 A’s
• Keystroke 3: A — 3 A’s
• Keystroke 4: Ctrl+A — selects all 3 A’s
• Keystroke 5: Ctrl+C — clipboard = 3, screen unchanged
• Keystroke 6: Ctrl+V — appends 3 more, screen = 6 A’s
• Keystroke 7: Ctrl+V — appends 3 more, screen = 9 A’s

DP check: dp[7] = dp[3] x (4-1) = 3 x 3 = 9. Block size j = 4 (CtrlA + CtrlC + 2 pastes).

N = 10 (two paths tie at 20)

Path A (j = 5, five-keystroke block):

• Keystrokes 1-5: A x5 — 5 A’s on screen
• Keystroke 6: Ctrl+A; Keystroke 7: Ctrl+C
• Keystroke 8: Ctrl+V — 5 + 5 = 10 A’s
• Keystroke 9: Ctrl+V — 10 + 5 = 15 A’s
• Keystroke 10: Ctrl+V — 15 + 5 = 20 A’s

DP check: dp[5] x (5-1) = 5 x 4 = 20.

Path B (j = 6, six-keystroke block):

• Keystrokes 1-4: A x4 — 4 A’s on screen
• Keystroke 5: Ctrl+A; Keystroke 6: Ctrl+C
• Keystroke 7: Ctrl+V — 8 A’s
• Keystroke 8: Ctrl+V — 12 A’s
• Keystroke 9: Ctrl+V — 16 A’s
• Keystroke 10: Ctrl+V — 20 A’s

DP check: dp[4] x (6-1) = 4 x 5 = 20.

Both paths satisfy the recurrence. The DP records the maximum, so ties don’t affect correctness.

Python Implementation

The DP solution runs in O(N squared) time and O(N) space:

def max_a(n):
    if n <= 6:
        return n

    dp = list(range(n + 1))  # dp[i] = i for i in 0..6

    for i in range(7, n + 1):
        for j in range(3, i):
            val = dp[i - j] * (j - 1)
            if val > dp[i]:
                dp[i] = val

    return dp[n]

# Verify against the table
for n in range(1, 13):
    print(n, max_a(n))
# Output: 1 1 / 2 2 / 3 3 / 4 4 / 5 5 / 6 6 / 7 9 / 8 12 / 9 16 / 10 20 / 11 27 / 12 36

The inner loop iterates j from 3 (minimum block: one Ctrl+A, one Ctrl+C, one Ctrl+V) to i minus 1 (leaving at least one earlier keystroke for building A’s). The array fills left to right; each cell uses only already-computed values.

Where This Problem Appears in Placement Rounds

The four-key problem sits at the intersection of DP recognition and careful counting, the combination that separates students in algorithmic coding rounds.

LeetCode lists it as problem 651 (Four Keys Keyboard) on the premium track. It also appears in FACE Prep’s internal problem bank and on GeeksForGeeks as a frequently cited interview question tagged under dynamic programming.

Companies that run dedicated algorithmic rounds include D.E. Shaw recruitment, where DP-heavy problems feature in the written test. The failure mode in placement rounds is the same as the greedy error shown earlier: starting the copy-paste block too soon, without evaluating how many keystrokes remain for the build phase. Recognising that structure as a dp-recurrence-over-suffix-blocks is the skill being assessed.

For systematic preparation across DP and other quantitative topics, the placement preparation resources guide is worth checking. It covers books and practice sets used in FACE Prep’s on-campus batches.

Tracing which j value maximises dp[N] for each input (the same process shown in the traced examples above) builds DP intuition faster than passively reading solutions. TinkerLLM at ₹299 gives you an LLM environment to step through that recurrence interactively, generate test cases for tricky values of N, and catch arithmetic slips before a coding round. The answer table above took three independent passes to verify; having a collaborator catch each step is faster than working alone.