Last Updated: 22 Jul, 2022
Smit’s String Flip Game.
Hard
Asked in company
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”.
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
Approaches
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’.
- If ‘i-1 >= 0’ and ‘i+1 < N’ and ‘STR[i-1] == STR[i+1]’.
- Assign ‘STR’ the value of ‘ANS’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Return ‘ANS’.
The main idea behind this approach is to find a cycle such that after applying some number of operations the string ‘STR’ returns to a state which has already been iterated.
If we find this cycle length, we don’t need to apply the operation ‘K’ times, we can easily find the remainder of ‘K’ to the length of the cycle (number of operations after which we again get the same string) and determine the final string. Because if there is a cycle of length ‘X’ then we can say that after ‘X’, ‘2*X’, ‘3*X’, … until <= ‘K’, the string ‘STR’ will remain the same.
Now we can also prove that this cycle length can at most be ‘2(N-2)’ using the pigeonhole principle. Because there can be at most ‘2N’ possible arrangements of ‘0’ and ‘1’ in string ‘STR’ after performing any number of operations, thus it is guaranteed that after at most ‘2N’ operations we will again reach the same string ‘STR’. And if we observe more accurately the first and last characters always become ‘0’ after applying the operations once. Thus the possible arrangements reduce to ‘2(N-2)’.
So in case ‘K < X’ then we can find the final string by brute force otherwise we can find the final string using above mentioned approach. We can use a HashMap to store the different states of string ‘STR’ we got after applying operations.
This solution is better than the O ( K * N ) brute force approach because for huge ‘K’ this solution reduces the operations to be performed because it keeps track of the previously visited strings and detects multiple cycles involved in the transformation process thus reducing the re-computation.
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’.
- Create a HashMap ‘STRINGS’ which can store strings.
- Run a while loop until ‘K>0’
- Insert ‘STR’ into HashMap ‘STRINGS’ with the key as ‘STR’ and value as ‘K’.
- Decrement ‘K’ by ‘1’.
- 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’.
- If ‘i-1 >= 0’ and ‘i+1 < N’ and ‘STR[i-1] == STR[i+1]’.
- Assign ‘STR’ the value of ‘ANS’.
- If ‘STR’ is present in ‘STRINGS’
- Initialize the variable ‘CYCLE’ with the value of the difference between the value corresponding to ‘STR’ in HashMap ‘STRINGS’ and the current ‘K’.
- Assign ‘K’ the value of the remainder of the division of ‘K’ and ‘CYCLE’.
- Return ‘ANS’.