Given binary string str, the task is to choose any index and change into 0 or 1, and do this in minimum steps such that the count of substring 01 is equal to 10.
Examples:
Input: str = “01101”
Output: 01100
Explanation: 01 as a substring repeat 2 times in a string, 10 as a substring repeat 1 times in a string. So, change last char 1 into 0 then count of 01 and 10 is 1 and equalInput: str = “01101010”
Output: 01101010
Approach: If we can observe that if the first and last character of the string is the same so the count of “01” is equal to 1 because by induction is always one character is present in the middle of the string so, we can split a string into two parts s[1….i], [i…n] so AB(s) = BA(s).
- If the first and last characters are not the same, then change the first character to the last character.
- After performing the above steps, print the value of str as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to make the count equalstring MakeEqual(string str){ // Take first and last char of string char FirstChar = str[0]; char LastChar = str[str.size() - 1]; // Compare both the char if (FirstChar != LastChar) { // Copy lastchar inplace of // firstchar or viceversa str[0] = LastChar; } // If above condition is not true so // string remain unchanged // Return string return str;}// Driver Codeint main(){ string str = "0110101"; string ans = MakeEqual(str); cout << ans; return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to make the count equal static String MakeEqual(String str) { // Take first and last char of String char FirstChar = str.charAt(0); char LastChar = str.charAt(str.length() - 1); // Compare both the char if (FirstChar != LastChar) { // Copy lastchar inplace of // firstchar or viceversa str = str.substring(1, str.length()); str = LastChar + str; } // If above condition is not true so // String remain unchanged // Return String return str; } // Driver Code public static void main(String args[]) { String str = "0110101"; String ans = MakeEqual(str); System.out.println(ans); }}// This code is contributed by saurabh_jaiswal. |
Python3
# python3 program for the above approach# Function to make the count equaldef MakeEqual(str): # Take first and last char of string FirstChar = str[0] LastChar = str[-1] # Compare both the char if (FirstChar != LastChar): # Copy lastchar inplace of # firstchar or viceversa str[0] = LastChar # If above condition is not true so # string remain unchanged # Return string return ''.join(str)# Driver Codeif __name__ == "__main__": str = "0110101" ans = MakeEqual(list(str)) print(ans) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG{ // Function to make the count equal static String MakeEqual(String str) { // Take first and last char of String char FirstChar = str[0]; char LastChar = str[str.Length - 1]; // Compare both the char if (FirstChar != LastChar) { // Copy lastchar inplace of // firstchar or viceversa str = str.Substring(1, str.Length - 1); str = LastChar + str; } // If above condition is not true so // String remain unchanged // Return String return str; } // Driver Code public static void Main(String []args) { String str = "0110101"; String ans = MakeEqual(str); Console.WriteLine(ans); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Function to make the count equal function MakeEqual(str) { // Take first and last char of string str = str.split('') let FirstChar = str[0]; let LastChar = str[str.length - 1]; // Compare both the char if (FirstChar != LastChar) { // Copy lastchar inplace of // firstchar or viceversa str[0] = LastChar; } // If above condition is not true so // string remain unchanged // Return string return str.join(''); } // Driver Code let str = "0110101"; let ans = MakeEqual(str); document.write(ans); // This code is contributed by Potta Lokesh</script> |
1110101
Time Complexity: O(1), The time complexity of this program is O(1) because it only performs constant operations like accessing characters in the string, comparing characters, and assigning new values to the string. Therefore, the time taken by the program will be the same for all input sizes.
Auxiliary Space: O(1), The space complexity of this program is O(1) because it only uses a fixed amount of memory to store the input string, two characters for the first and last characters of the string, and a string variable to store the modified string. Therefore, the space used by the program will remain constant for all input sizes.
