Senior Software Engineer

Given a string (STR) of length N, you have to create a new string by performing the following operation:

Take the smallest character from the first 'K' characters of STR, remove it from STR and append it to the new string.

You have to perform this operation until STR is empty.

 Note:

The input string(STR) will not contain any spaces.

Assume that all characters in STR are lower case letters.

If characters less than 'K' remain, then append them in a sorted way to the new string.

Example:

Let the input string be "edcba" with K = 4.

Let the new string to be formed is initially empty, newString = "".
The first set of 4 characters are, ('e', 'd', 'c', 'b')
Out of these 4 characters, the smallest one is 'b' and hence we add it to the newString and it becomes, 
newString = "b"

The next set of 4 characters are, ('e', 'd', 'c', 'a')
Out of these 4 characters, the smallest one is 'a' and hence we add it to the newString and it becomes, 
newString = "ba"

Now we are left with "edc" and since we can't get a window of size 4, we sort them in the increasing order and append them to the newString.

Hence, newString thus formed will be "bacde".

You are given an array ‘ARR’ of size ‘N,’ and you have to tell the minimum number of elements that need to be removed such that the array contains all distinct elements. More formally, there should not be any ‘I’ and ‘J’ such that ‘I’ != ‘J’ and ‘ARR’[‘I’] = ‘ARR’[‘J’].

For example:

Given ‘N’ = 4, 
'ARR' = { 1, 2, 1, 2} 
Then the answer is 2 because 1 and 2 are repeated once therefore we need to remove 2 elements.

Related to DSA , Design Principles, SOLID , OOPs