2 Keys Keyboard - Leetcode Solution

Problem statement: Suppose you have a special keyboard with the following keys:

Key 1: (A): Print one 'A' on the screen. Key 2: (Ctrl-A): Select the whole screen. Key 3: (Ctrl-C): Copy selection to buffer. Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), you need to write a program to produce maximum number of 'A's. Print the maximum number of 'A's on the screen after N presses.

Example 1: 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: 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: The problem requires us to press keys for N times to generate maximum number of 'A's. We need to keep track of the maximum number of 'A's that we can get for each value of N.

We can use dynamic programming technique to solve this problem. We can start with a state 'cur' = 0, which represents an empty screen. At each step, we can either press the 'A' key, or the Ctrl-V key depending on the current state.

If we press 'A', the current number of 'A's on the screen is increased by 1. If we press Ctrl-V, the current number of 'A's on the screen is multiplied by the number of times it has been pasted. This can be achieved by maintaining a copy of the last state as well as the number of times it has been pasted, and then updating the new state by appending copy k times, where k is the number of times it has been pasted.

To maximize the number of 'A's on screen, we need to keep track of the maximum number of 'A's for each value of N. Thus, we can use an array maxval[] to store the maximum number of 'A's we can get for each value of N.

The time complexity of this algorithm is O(N^2), since we need to iterate over all values of k from 1 to N-3 for each value of N. The space complexity is O(N), since we only need to store the maximum number of 'A's for each value of N.

Here is the Python code for the solution:

def maxA(N): dp = [0] * (N+1) for i in range(1, N+1): dp[i] = dp[i-1] + 1 # Press A for j in range(2, i): dp[i] = max(dp[i], dp[j-2] * (i-j+1)) return dp[N]

1