String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


Special Keyboard

Special Keyboard: In this article we are going to see an interview problem that is special keyboard problem and its solution – which has been featured in Amazon interview rounds.
Submitted by Radib Kar, on June 09, 2020

Problem statement

Imagine you have a special keyboard with four types of keys:

Key 1: Prints 'I' on screen

Key 2: Select whatever printed in screen

Key 3: Copy selection to buffer

Key 4: Append buffer on-screen after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of I's possible to be printed on the screen.


Input is N, number of times keys can be pressed in total.


Print maximum number of I's possible to print


1 ≤ N ≤ 75




We can at most get 2 I's on screen by pressing 
following key sequence Key1, key1.
Pressing other keys have no effect. 
Like key 1, key2 will produce only one I on screen. 



We can at most get 9 I's on screen by pressing 
following key sequence.
Key1, Key1, Key1, Key2, Key3, key4, Key4

I //after pressing key1
I I  //again pressing key 1
I I I //again pressing key1
I I I //pressing key2 selects three I's
I I I // pressing key3 copies these three I's to buffer
I I I I I I // pressing key4 appends these three I's 
I I I I I I I I I // pressing key4 again appends these three I's 

Solution Approach


Two things need to be understood to solve this problem

Key4 appends whatever is printed already on screen before 3 key pressing

That means at moment 4,

You can append whatever was printed while moment 1 as to print in moment 4, you need to press key2 at moment 2 and key3 at moment 3.

So, the recursive function can be written as


F(n) = max number of I’s printed on screen

So, for n>3

F(n) = max(f(j)*(n-j-1)) for 1<=j<=n-3

F(j) = already printed characters up to moment j 
and (n-j-1) is number of appending possible   

So, now we need to convert the recursion into DP.

1)  Initialize dp[n+1] like following base value;
2)  for i=0 to n
3)  Fill the DP table
        for i=4 to n
            for j=i-3 to 1,j--
            end for
        End for
4)  Return dp[n]

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int specialKeyboard(int n)

    int dp[n + 1];
    for (int i = 0; i <= n; i++)
        dp[i] = i;

    for (int i = 6; i <= n; i++) {
        for (int j = i - 3; j >= 1; j--) {
            dp[i] = std::max(dp[i], dp[j] * (i - j - 1));

    return dp[n];

int main()
    int t, n, item;

    cout << "Input n, number of times keys to be pressed: ";
    scanf("%d", &n);
    cout << "max no of i's got printed: " << specialKeyboard(n) << endl;

    return 0;


Input n, number of times keys to be pressed: 7
max no of i's got printed: 9

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.