String Transformation

Moderate
0/80
Average time to solve is 23m
profile
Contributed by
20 upvotes
Asked in companies
SprinklrWalmartBNY Mellon

Problem statement

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".
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only line of each test case or query contains a string(STR) and an integer(K) separated by a single space.
Output Format : 
For each test case, print the new string formed by applying the operations.

Output for every test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints : 
1 <= t <= 100
0 <= N <= 10^5
1 <= K <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
badce 2
abe 2
Sample Output 1 :
abcde
abe
Explanation For Sample Input 1:
For the 1st test case:
The smallest character of the string is 'a', followed by 'b', 'c', 'd', and 'e' respectively. Hence the output string is "abcde".

For the 2st test case:
The smallest character of the string is 'a', followed by 'b', and 'e' respectively. Hence the output string is "abe".
Sample Input 2 :
1
codingninjas 3
Sample Output 2 :
cdigninjanos
Hint

Try exploring every window of K elements and try to pick the smallest character.

Approaches (2)
Brute Force Approach
  • Create a new “answer” string that will contain the modified string
  • While the input string's length is greater than 0
    • Find the minimum character in the first K characters of the string (or the entire string if its length is less than K)
    • Append that character to the “answer” string
    • Remove that character from the input string
  • Return the “answer” string
Time Complexity

O(N * (N + K)), where K is the window size and N is the length of the input string

 

As we iterate through the entire string N times.

Space Complexity

O(1)

 

Since we are using constant space.

Code Solution
(100% EXP penalty)
String Transformation
Full screen
Console