Given a binary string S of size N and a positive integer K, the task is to repeatedly modify the given string K number of times by flipping all the 0s having different adjacent characters in each iteration.
Note: For the character 0 present at 0th index then it will change to 1 only when 1st index character is 1 and if the last index character is 0 then it changes to ‘1’ if the second last index character is ‘1’.
Examples:
Input: S = “01001”, K = 2
Output: 11111
Explanation:
Below are the operation performed K(= 2) number of times:|
Operation 1: After flipping the string at indices 0, 2, 3, the string modifies to “11111”.
Operation 2: There is no such possible flipping for the modified string S = “11111”.
After the above operations, the modified string is “11111”.Input: S = “10010001”, K = 3
Output: 11111011
Approach: The given problem can be solved by performing the given operation K number of times and then print the resultant string formed. Follow the steps below to solve this problem:
- Iterate over the range [0, K – 1] using the variable i and perform the following steps:
- Traverse the given string S over the range [0, N – 1] using the variable j and perform the following steps:
- If the character at 0th index is 0, then replace this value with the first index value.
- Otherwise, if character 0 is present at the last index then replace this value with the second last index character.
- Otherwise, convert all the 0s to 1 if the adjacent characters are different.
- After the above steps, if the string remains the same before the modification, then break out of the loop.
- Traverse the given string S over the range [0, N – 1] using the variable j and perform the following steps:
- After completing the above steps, print the string S as the resultant modified string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to modify the given string// K number of times by flipping 0s// having different adjacent charactersvoid convertString(string S, int k){ // Size of the string int n = S.length(); // Stores modified string after // each iteration string temp = S; // Iterate over the range [0 k] for (int i = 0; i < k; i++) { // Traverse the string S for (int j = 0; j < n; j++) { // If '0' is present at // 0th index then replace // it with 1st index if (j == 0 && S[j] == '0') { temp[j] = S[j + 1]; } // If '0' is present at the // last index then replace // it with last index - 1 // character else if (j == n - 1 && S[j] == '0') { temp[j] = S[j - 1]; } // Otherwise, convert 0s // to 1 if the adjacent // characters are different else if (S[j - 1] != S[j + 1] && S[j] == '0') { temp[j] = '1'; } } // If during this iteration // there is no change in the // string then break this loop if (S == temp) { break; } // Update the string S S = temp; } // Print the updated string cout << S;}// Driver Codeint main(){ string S = "10010001"; int K = 1; convertString(S, K); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;import java.util.*; class GFG{ // Function to modify the given string // K number of times by flipping 0s // having different adjacent characters public static void convertString(String Str,int k) { // Size of the string int n = Str.length(); // Stores modified string after // each iteration char[] S = Str.toCharArray(); char[] temp = Str.toCharArray(); // Iterate over the range [0 k] for (int i = 0; i < k; i++) { // Traverse the string S for (int j = 0; j < n; j++) { // If '0' is present at // 0th index then replace // it with 1st index if (j == 0 && S[j] == '0') { temp[j] = S[j + 1]; } // If '0' is present at the // last index then replace // it with last index - 1 // character else if (j == n - 1 && S[j] == '0') { temp[j] = S[j - 1]; } // Otherwise, convert 0s // to 1 if the adjacent // characters are different else if(j<n-1 && j>0) { if (S[j - 1] != S[j + 1] && S[j] == '0') { temp[j] = '1'; } } } // If during this iteration // there is no change in the // string then break this loop if (S == temp) { break; } // Update the string S S = temp; } // Print the updated string System.out.println(S); } // Driver Code public static void main(String[] args) { String S = "10010001"; int K = 1; convertString(S, K); }}// this code is contributed by aditya942003patil |
Python3
# python 3 program for the above approach# Function to modify the given string# K number of times by flipping 0s# having different adjacent charactersdef convertString(S, k): # Size of the string n = len(S) # Stores modified string after # each iteration temp = S temp = list(temp) # Iterate over the range [0 k] for i in range(k): # Traverse the string S for j in range(n-1): # If '0' is present at # 0th index then replace # it with 1st index if (j == 0 and S[j] == '0'): temp[j] = S[j + 1] # If '0' is present at the # last index then replace # it with last index - 1 # character elif (j == n - 1 and S[j] == '0'): temp[j] = S[j - 1] # Otherwise, convert 0s # to 1 if the adjacent # characters are different elif (S[j - 1] != S[j + 1] and S[j] == '0'): temp[j] = '1' # If during this iteration # there is no change in the # string then break this loop if (S == temp): break temp = ''.join(temp) # Update the string S S = temp # Print the updated string print(S)# Driver Codeif __name__ == '__main__': S = "10010001" K = 1 convertString(S, K) # This code s contributed by ipg2016107. |
C#
//C# implementation of above approachusing System;using System.Text;public class GFG { static void convertString(string S, int k) { // Size of the string int n = S.Length; // Stores modified string after // each iteration StringBuilder temp = new StringBuilder(S); // Iterate over the range [0 k] for (int i = 0; i < k; i++) { // Traverse the string S for (int j = 0; j < n; j++) { // If '0' is present at // 0th index then replace // it with 1st index if (j == 0 && S[j] == '0') { temp[j] = S[j + 1]; } // If '0' is present at the // last index then replace // it with last index - 1 // character else if (j == n - 1 && S[j] == '0') { temp[j] = S[j - 1]; } // Otherwise, convert 0s // to 1 if the adjacent // characters are different else if (j>0 && j<n-1 && S[j - 1] != S[j + 1] && S[j] == '0') { temp[j] = '1'; } } // If during this iteration // there is no change in the // string then break this loop string t = temp.ToString(); if (S == t) { break; } // Update the string S S = t; } // Print the updated string Console.Write(S); } // Driver program to test above public static void Main() { string S = "10010001"; int K = 1; convertString(S, K); }}// This code is contributed by aditya942003patil |
Javascript
<script>// JavaScript program for the above approach// Function to modify the given string// K number of times by flipping 0s// having different adjacent charactersfunction convertString(S, k){ // Size of the string let n = S.length; // Stores modified string after // each iteration let temp = S; // Iterate over the range [0 k] for (let i = 0; i < k; i++) { // Traverse the string S for (let j = 0; j < n; j++) { // If '0' is present at // 0th index then replace // it with 1st index if (j == 0 && S[j] == '0') { temp[j] = S[j + 1]; } // If '0' is present at the // last index then replace // it with last index - 1 // character else if (j == n - 1 && S[j] == '0') { temp[j] = S[j - 1]; } // Otherwise, convert 0s // to 1 if the adjacent // characters are different else if (S[j - 1] != S[j + 1] && S[j] == '0') { temp = temp.substring(0,j)+'1'+temp.substring(j+1); } } // If during this iteration // there is no change in the // string then break this loop if (S == temp) { break; } // Update the string S S = temp; } // Print the updated string document.write(S);}// Driver Codelet S = "10010001";let K = 1;convertString(S, K);// This code is contributed by shinjanpatra</script> |
Output : 11111011
Time Complexity: O(N*K)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
