Problem

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.

Examples

Example 1

1
2
3
4
5

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2

1
2
3
4
5

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

Solution

Method 1 – Dynamic Programming

Intuition

The key idea is to use dynamic programming to find the optimal sequence of key presses. At each step, we decide whether to press ‘A’ or to perform a sequence of ‘Ctrl-A’, ‘Ctrl-C’, and multiple ‘Ctrl-V’s to maximize the number of ‘A’s. The optimal solution at each step depends on the best result from previous steps.

Approach

  1. Create a DP array dp where dp[i] represents the maximum number of ‘A’s that can be produced with i key presses.
  2. For each i from 1 to n:
  • Set dp[i] = dp[i-1] + 1 (pressing ‘A’).
  • For each possible earlier position j (where j ranges from 2 to i-1):
    • Perform ‘Ctrl-A’ and ‘Ctrl-C’ at step j-2, then paste (i-j+1) times.
    • Update dp[i] = max(dp[i], dp[j-2] * (i-j+1)).
  1. Return dp[n] as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   public int maxA(int n) {
      int[] dp = new int[n + 1];
      for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        for (int j = 2; j < i; j++) {
           dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
        }
      }
      return dp[n];
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from typing import List

class Solution:
   def maxA(self, n: int) -> int:
      dp: List[int] = [0] * (n + 1)
      for i in range(1, n + 1):
        dp[i] = dp[i - 1] + 1
        for j in range(2, i):
           dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
      return dp[n]

Complexity

  • ⏰ Time complexity: O(n^2) — For each i, we may check up to i previous positions.
  • 🧺 Space complexity: O(n) — For the DP array.