651. 4 Keys Keyboard


Problem Description

Imagine you are given a special text editor which only has four keys:

  • A: This key simply prints one 'A' character on the screen.
  • Ctrl-A: This key selects everything that is currently on the screen.
  • Ctrl-C: This key is used to copy the selected text into a buffer. This buffer holds the copied text until it is overwritten by a subsequent use of Ctrl-C.
  • Ctrl-V: This key pastes the content of the buffer onto the screen immediately after what's already displayed.

Your task is to figure out the maximum number of 'A's that you can print on the screen if you are allowed to press the keys a total of n times. The problem is essentially to find the optimal way to use these key presses to maximize the number of 'A's.

Intuition

To arrive at the solution, we should think about the optimal sequence of key presses as n grows larger. Initially, pressing A is our only option. However, once we have the ability to use Ctrl-A, Ctrl-C, and Ctrl-V, we need to strategically decide when to use these to multiply the amount of 'A's we display.

Pasting (Ctrl-V) is only useful if we've copied (Ctrl-C) a significant amount of 'A's to begin with. Moreover, for each sequence involving Ctrl-A, Ctrl-C, followed by multiple Ctrl-V presses, there is a point where the best move is to start a new sequence of Ctrl-A, Ctrl-C, then Ctrl-Vs rather than continuing to Ctrl-V.

The solution involves using dynamic programming to keep track of the best possible outcome for each number of presses up to n. The dp array represents the maximum number of 'A's we can get for every number of key presses from 0 to n. The formula dp[i] = max(dp[i], dp[j - 1] * (i - j)) updates the dp[i] with the maximum value between the current dp[i] and the product of dp[j - 1] and (i - j). Here, dp[j - 1] represents the number of 'A's before we press Ctrl-A, Ctrl-C, and (i - j) represents the number of times we can press Ctrl-V after i - j - 2 key presses spent on selecting and copying.

By iterating through all possible breakpoints for copying and pasting, the algorithm ensures that it finds the maximum number of 'A's possible for each total number of key presses.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution employs dynamic programming, which is an optimization technique used to solve problems by breaking them down into simpler subproblems. Here, the goal is to maximize the number of 'A's that can be printed with a given number of key presses.

The implementation defines a dp array of size n + 1, where each element at index i holds the maximum number of 'A's that can be printed using i key presses. The initial values in the dp array are set equal to their indices, which corresponds to pressing the 'A' key as many times as possible without using any other keys.

The key idea is to consider that, for each position i in the dp array, the maximum number of 'A's dp[i] can be obtained by:

  • Using the first j-1 presses to get a certain number of 'A's (denoted as dp[j-1])
  • Then, using one press to Ctrl-A, one press to Ctrl-C, and the remaining i - j presses to Ctrl-V multiple times to double, triple, or further multiply the number of 'A's we had at dp[j-1]

This is expressed in the code as:

1dp[i] = max(dp[i], dp[j - 1] * (i - j))

This line iterates through all potential breakpoints j, where we switch from pressing 'A' to using the Ctrl-A, Ctrl-C, and then Ctrl-V sequence. For each j, it considers the number of 'A's we had at j-1 presses, and multiplies this by the number of times we can paste, which is i - j.

The loops in the code are constructed as follows:

  1. The outer loop goes from 3 to n+1 because we need at least 3 key presses to perform the full sequence of Ctrl-A, Ctrl-C, and Ctrl-V at least once.
  2. The inner loop tries to find the optimal point j where we should switch from pressing 'A' to using the multi-press sequence. It runs from 2 to i-1.

The process continues until we check all possible combinations of key presses up to n. The final answer is the last element of the dp array, which contains the maximum number of 'A's for n key presses.

1class Solution:
2    def maxA(self, n: int) -> int:
3        dp = list(range(n + 1))
4        for i in range(3, n + 1):
5            for j in range(2, i - 1):
6                dp[i] = max(dp[i], dp[j - 1] * (i - j))
7        return dp[-1]

With this approach, the solution maximizes the output by finding the best time to perform each action, resulting in the highest number of 'A's possible.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's consider an example where the total number of key presses allowed is n = 7. We will walk through the dynamic programming approach explained in the solution to understand how we can maximize the number of 'A's printed.

  1. Initialize dp array with the number of key presses because the minimum we can do is press the 'A' key n times, hence dp = [0, 1, 2, 3, 4, 5, 6, 7].
  2. The first 3 key presses would go in the normal way – printing 'A' three times since we need at least 3 key presses to start using the Ctrl-A, Ctrl-C, Ctrl-V sequence. So, dp[1] = 1, dp[2] = 2, and dp[3] = 3.
  3. Now, for i = 4, we have two options: either press 'A' one more time to have dp[4] = 4 or do the sequence Ctrl-A, Ctrl-C, and Ctrl-V to double the 2 'A's we had at dp[2]. This would give us dp[4] = dp[2] * (4 - 2) = 2 * 2 = 4. We pick the maximum, which is still 4.
  4. For i = 5, again we could press 'A' (dp[5] = 5) or use the sequence Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V. There are now two places this sequence might start:
    • After 1 'A' (dp[1]) and then paste it 3 times (i - 2), giving us dp[5] = dp[1] * (5 - 2) = 1 * 3 = 3, or
    • After 2 'A's (dp[2]) and then paste 2 times, giving us dp[5] = dp[2] * (5 - 3) = 2 * 2 = 4. The maximum is dp[5] = 5, so we keep it as is.
  5. For i = 6, we consider starting the sequence after having 1, 2, or 3 'A's and then using Ctrl-V:
    • dp[6] = dp[1] * (6 - 2) = 1 * 4 = 4 (starting after 1 'A')
    • dp[6] = dp[2] * (6 - 3) = 2 * 3 = 6 (starting after 2 'A's)
    • dp[6] = dp[3] * (6 - 4) = 3 * 2 = 6 (starting after 3 'A's) The maximum we can get is dp[6] = 6, and as it's equal to simply pressing 'A' six times, no change is made.
  6. Finally, for i = 7, we check the same as above, considering where to start the sequence:
    • dp[7] = dp[1] * (7 - 2) = 1 * 5 = 5 (starting after 1 'A')
    • dp[7] = dp[2] * (7 - 3) = 2 * 4 = 8 (starting after 2 'A's)
    • dp[7] = dp[3] * (7 - 4) = 3 * 3 = 9 (starting after 3 'A's)
    • dp[7] = dp[4] * (7 - 5) = 4 * 2 = 8 (starting after 4 'A's) The best we can do is start the sequence after having 3 'A's, leading to dp[7] = 9.

So, the maximum number of 'A's we can print with 7 key presses is dp[7] = 9. The solution identifies that it's more efficient to start the Ctrl-A, Ctrl-C, Ctrl-V sequence after having pressed 'A' three times, and then use the remaining key presses to multiply these 'A's.

Solution Implementation

1class Solution:
2    def maxA(self, n: int) -> int:
3        # Initialize a list `dp` with values equal to the indexes 
4        # as the max achievable by direct A keypresses
5        dp = list(range(n + 1))
6      
7        # Start from the 3rd index because the first two do not need any calculations
8        for i in range(3, n + 1):
9            # Loop over the range to find out the breaking point for optimal
10            # CTRL-V presses after a CTRL-A, CTRL-C sequence.
11            for j in range(2, i - 1):
12                # Calculate the max between current dp value and the sequence
13                # of selecting all (dp[j - 1]), copying and pasting (i - j) times.
14                # i-j represents the remaining key presses after (j-1) presses are used 
15                # to reach optimal select and copy.
16                dp[i] = max(dp[i], dp[j - 1] * (i - j))
17        # Return the last element which contains the maximum number of 'A's that can be produced
18        return dp[-1]
19
1class Solution {
2    // Function to find out maximum number of 'A's that can be produced by
3    // pressing keys in a certain order, given a limit of key presses
4    public int maxA(int n) {
5        // Initialize an array to store the subproblem results
6        int[] dp = new int[n + 1];
7
8        // Base case: For i presses, you can at most get i 'A's by pressing 'A' i times
9        for (int i = 0; i <= n; ++i) {
10            dp[i] = i;
11        }
12
13        // Start filling dp table for each number of presses (index)
14        for (int i = 3; i <= n; ++i) {
15            // Explore the effect of using Ctrl-V after pressing Ctrl-A and Ctrl-C
16            // starting from j=2 as you need at least one 'A' for Ctrl-A and Ctrl-C to make sense
17            for (int j = 2; j < i - 1; ++j) {
18                // Calculate the maximum of either just pressing 'A'
19                // or using a combination of Ctrl-A, Ctrl-C, and Ctrl-V
20                // dp[j - 1] represents the number of 'A's on the screen before copying,
21                // (i - j) represents the remaining number of presses after copying which is used solely for pasting
22                // the product of those two numbers represent the total 'A's after utilizing the copy-paste operation
23                dp[i] = Math.max(dp[i], dp[j - 1] * (i - j));
24            }
25        }
26
27        // The last element of dp array contains the answer for n key presses
28        return dp[n];
29    }
30}
31
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // The maxA function calculates the maximum number of 'A's that can
7    // be produced by pressing keys on the keyboard for 'n' times.
8    int maxA(int n) {
9        // Initialize a dynamic programming array to store the intermediate results.
10        // dp[i] represents the maximum number of 'A's that can be produced by pressing
11        // keys i times.
12        std::vector<int> dp(n + 1);
13      
14        // The base cases: If you press i times, the maximum you can get is i 'A's,
15        // by pressing the key 'A' i times (for first two i's). For i > 2,
16        // you might get more by using Ctrl-A, Ctrl-C, and Ctrl-V.
17        std::iota(dp.begin(), dp.end(), 0);
18      
19        // Loop through each possible number of presses from 3 to n
20        for (int i = 3; i <= n; ++i) {
21            // Check all the possibilities of the last sequence of "Ctrl-A, Ctrl-C followed by
22            // Ctrl-V's". The Ctrl-A, Ctrl-C must be at some point j before i, and the remaining
23            // presses (i - j) are for Ctrl-V.
24            for (int j = 2; j < i - 1; ++j) {
25                // The number of 'A's after pressing Ctrl-V (i - j times) following a copy operation
26                // at j-th press will be the number of 'A's at (j - 1) multiplied by (i - j).
27                // We update dp[i] if this yields more 'A's than we've seen for i presses.
28                dp[i] = std::max(dp[i], dp[j - 1] * (i - j));
29            }
30        }
31      
32        // After filling dp array, the answer for n presses is at dp[n].
33        return dp[n];
34    }
35};
36
1// Initialize a global dynamic programming array to store the intermediate results.
2// dp[i] represents the maximum number of 'A's that can be produced by pressing
3// keys i times.
4const dp: number[] = [];
5
6// The maxA function calculates the maximum number of 'A's that can
7// be produced by pressing keys on the keyboard for 'n' times.
8function maxA(n: number): number {
9    // Resize the dp array to store results for up to n key presses.
10    dp.length = n + 1;
11
12    // The base case configurations: If you press i times, the maximum you can get is i 'A's,
13    // by pressing the 'A' key i times (for the first few i's).
14    for (let i = 0; i <= n; i++) {
15        // This simulates pressing the 'A' key i times.
16        dp[i] = i;
17    }
18
19    // Loop through each possible number of presses from 3 to n
20    for (let i = 3; i <= n; i++) {
21        // Check all possibilities where the last sequence of keys pressed is
22        // "Ctrl-A, Ctrl-C followed by Ctrl-V's". The Ctrl-A, Ctrl-C must
23        // happen at some point j before i, so the remaining
24        // presses (i - j) are for Ctrl-V.
25        for (let j = 2; j < i - 1; j++) {
26            // Any sequence of operations ending with Ctrl-A, Ctrl-C and (i - j) Ctrl-Vs
27            // results in the screen containing the clipboard contents repeated (i - j) times.
28            // So the optimal sequence length at this state is the number of 'A's that
29            // can be produced by j - 1 presses times (i - j) for the subsequent Ctrl-V presses.
30            const current = dp[j - 1] * (i - j);
31
32            // Update dp[i] to the maximum number of 'A's seen after i presses.
33            dp[i] = Math.max(dp[i], current);
34        }
35    }
36
37    // After filling out the dp array, the answer for n presses is at dp[n].
38    return dp[n];
39}
40
41// Example usage:
42// let result = maxA(7); // Should calculate the maximum number of 'A's for 7 key presses
43

Time and Space Complexity

The time complexity of the provided code is O(n^3). This is because there are two nested loops where the outer loop runs from 3 to n (in the range of n-2 iterations), and the inner loop runs from 2 up to i-1, which in the worst case is n-3 iterations for the inner loop when i is at its maximum. Since the inner loop is nested within the outer loop, we multiply the number of iterations of both these loops leading to (n-2)*(n-3) for the worst case, and since there is another constant operation inside the inner loop, it results in an overall cubic complexity.

The space complexity of the code is O(n). This is because the code uses a one-dimensional list, dp, that stores a value for each integer from 0 to n. The size of this list scales linearly with the value of n, hence the space complexity is directly proportional to n.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄