Smit’s String Flip Game.

Hard
0/120
Average time to solve is 50m
profile
Contributed by
0 upvote
Asked in company
Fareportal

Problem statement

Smit has been given a string ‘STR’ of length ‘N’, which only consists of ‘0’ and ‘1’ and an operation to be performed ‘K’ times on the string.

The operation description is as follows:

For every ‘i’ from ‘0’ <= ‘i’ < ‘N’, if there exist indices ‘(i-1)’ and ‘(i+1)’ such that ‘STR[i-1] = STR[i+1]’ then set the value of ‘STR[i]’ to ‘1’. If ‘(i-1)’ or ‘(i+1)’ is out of the index range or ‘STR[i-1]’ != ‘STR[i+1]’ then set ‘STR[i]’ to ‘0’.

For e.g. if ‘STR’ = “0000”, then after the operation the string ‘STR’ will be transformed to “0110” because for ‘i’ = ‘1’ and ‘i’ = ‘2’ the condition mentioned above is satisfied.

Note: When transforming we take into account the values of the old string given in the problem or we received after the application of the last operation not the newly transformed string in the current operation.

He has got an answer but is not completely sure if it is correct. So being, his friend he asked you to help him verify if his answer is correct or not. Can you help Smit to determine the correct string ‘STR’ after ‘K’ above-mentioned operations?.

EXAMPLE : 
Input: ‘N’ = 5, ‘K’ = 1, ‘STR’ = “10101”

Output: 01110
In this case, the indices satisfying the condition of ‘STR[i-1] = STR[i+1]’ are ‘1’, ‘2’, and ‘3’. Hence the string ‘STR’ after applying the given operation for ‘K(=1)’ times will be “01110”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer ‘T’, the number of test cases.

Each test case consists of two lines.

The first line of input contains three integers, ‘N’ and ‘K’, denoting the length of the given string ‘STR’ and the number of times the given operation is to be performed.

Followed by a line containing a string of length ‘N’ denoting the string ‘STR’, consisting of only ‘0’ and ‘1’.
Output format : 
For each test case, print the final string after applying ‘K’ operations.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
0 <= ‘K’ <= 10^9
It is guaranteed that the string ‘STR’ only consists of the character ‘0’ and ‘1’.

Time Limit: 1 sec
Sample Input 1 :
2
2 10
11
8 4
01011001
Sample Output 1 :
00
00000100
Explanation Of Sample Input 1 :
For the first test case, there doesn’t exist index ‘i-1’ for ‘0’th index and similarly, there doesn’t exist index ‘i+1’ for ‘1’st index. Hence after applying the operation once the string will remain the same after any number of operations.

Hence, the output will be: 00

For the second test case, the different states of string ‘STR’ after applying the operations one by one are as follows:
Operation 1: ‘STR’ = “01100000”.
Operation 2: ‘STR’ = “00001110”.
Operation 3: ‘STR’ = “01100100”.
Operation 4: ‘STR’ = “00000100”.

Hence, the output will be: 00000100
Sample Input 2 :
2
1 10000
1
5 1000000
10110
Sample Output 2 :
0
00100
Hint

Can we try to apply the given operations one by one?.

Approaches (2)
Brute Force

The idea for this approach is to apply the given operations one by one by creating a separate transformed string from the original string and replacing it at the end of the iteration.
 

We will do the above-mentioned approach ‘K’ times to get the final string ‘STR’.
 

Algorithm:
 

// The function will return the final string ‘STR’ after applying the given operation ‘K’ times.

String finalString(N, K, STR)

  • Create a string ‘ANS’ with the value of ‘STR’.
  • Run a for loop from ‘1’ to ‘K’ with a variable named ‘currOperation’.
    • Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
      • If ‘i-1 >= 0’ and ‘i+1 < N’ and ‘STR[i-1] == STR[i+1]’.
        • Assign ‘ANS[i]’ value of character ‘1’.
      • Else
        • Assign ‘ANS[i]’ value of character ‘0’.
    • Assign ‘STR’ the value of ‘ANS’.
  • Return ‘ANS’.
Time Complexity

O( K * N ), Where ‘N’ and ‘K’ are input integers.

In the above approach, we iterate from ‘1’ to ‘K’ and apply the mentioned approach to string ‘STR’ by iterating through it every time, which in total makes ‘N*K’ iterations.

Hence the time complexity will be O( N * K ).

Time Complexity is language dependent as in python strings are immutable so creating the ‘ans’ string will take O ( ‘N’ ) extra time so for python time complexity will be O( K * N * N ).

Space Complexity

O(N), Where ‘N’ is the input integer.

 

In the above approach, a string ‘ANS’ of length ‘N’ is used to temporarily store the state of the string ‘STR’ after the transformation operation,  

Hence the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Smit’s String Flip Game.
Full screen
Console