Skip to content

651. 4 Keys Keyboard πŸ”’

Description

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.

 

Example 1:

Input: n = 3
Output: 3
Explanation: We can at most get 3 A's on screen by pressing the 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

 

Constraints:

  • 1 <= n <= 50

Solutions

Solution 1

Thinking

With Select-All and Copy, an optimal sequence types some As and then pastes. Enumerating key strings is unnecessary.

\(dp[i]\) is the most As with \(i\) keystrokes: either \(i\) typed As, or Ctrl-A at \(j\) then paste \(i-j\) times, giving \(dp[j-1]\times(i-j)\).

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxA(int n) {
        vector<int> dp(n + 1);
        iota(dp.begin(), dp.end(), 0);
        for (int i = 3; i < n + 1; ++i) {
            for (int j = 2; j < i - 1; ++j) {
                dp[i] = max(dp[i], dp[j - 1] * (i - j));
            }
        }
        return dp[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func maxA(n int) int {
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = i
    }
    for i := 3; i < n+1; i++ {
        for j := 2; j < i-1; j++ {
            dp[i] = max(dp[i], dp[j-1]*(i-j))
        }
    }
    return dp[n]
}

Comments