# Find the maximum occurring character after performing the given operations

Given a string **str** consisting of **0, 1**, and** ***, the task is to find the maximum occurring character out of **0** and **1** after performing the given operations:

- Replace
*with0where*appears on the left side of the existing0s in the string.- Replace
*with1where*appears on the right side of the existing1s in the string.- If any
*can be replaced by both0and1, then it remains unchanged.

**Note: **If the frequency of 0 and 1 is same after performing the given operations then print **-1**.

**Examples:**

Input:str = “**0**1***0”Output:0Explanation:

Since0can replace the*to its left and1can replace the*to its right thus string becomes 000**1***0

Input:str = “0*1”Output:-1Explanation:

Both 0 and 1 have the same frequency hence the output is -1.

**Approach: **The idea to generate the final resultant string and then compare the frequency of 0 and 1. Below are the steps:

- Count the initial frequencies of 0 and 1 in the string and store them in variables say
**count_0**and**count_1**. - Initialize a variable, say
**prev**, as -1. Iterate over the string and check if the current character is*****. If so, then continue. - If it is the first character encountered and is
**0**then add all*****to**count_0**and change**prev**to current index. - Otherwise, if the first character is
**1**then change**prev**to current index. - If the previous character is
**1**and the current character is**0**then add half of*****in between the characters to**0**and half to**1**. - If the previous character is 0 and the current character is
**1**then no*****character in between them can be replaced. - If the previous and current both characters are of the same type then add the count of
*****to the frequencies. - Compare the frequencies of
**0**and**1**and print the maximum occurring character.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// Function to find the ` `// maximum occurring character ` `void` `solve(string S) ` `{ ` ` ` `// Initialize count of ` ` ` `// zero and one ` ` ` `int` `count_0 = 0, count_1 = 0; ` ` ` ` ` `int` `prev = -1; ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = 0; i < S.length(); i++) { ` ` ` ` ` `// Count the zeros ` ` ` `if` `(S[i] == ` `'0'` `) ` ` ` `count_0++; ` ` ` ` ` `// Count the ones ` ` ` `else` `if` `(S[i] == ` `'1'` `) ` ` ` `count_1++; ` ` ` `} ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = 0; i < S.length(); i++) { ` ` ` ` ` `// Check if character ` ` ` `// is * then continue ` ` ` `if` `(S[i] == ` `'*'` `) ` ` ` `continue` `; ` ` ` ` ` `// Check if first character ` ` ` `// after * is X ` ` ` `else` `if` `(S[i] == ` `'0'` `&& prev == -1) { ` ` ` ` ` `// Add all * to ` ` ` `// the frequency of X ` ` ` `count_0 = count_0 + i; ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if first character ` ` ` `// after * is Y ` ` ` `else` `if` `(S[i] == ` `'1'` `&& prev == -1) { ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev character is 1 ` ` ` `// and current character is 0 ` ` ` `else` `if` `(S[prev] == ` `'1'` `&& S[i] == ` `'0'` `) { ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 0 ` ` ` `count_0 = count_0 + (i - prev - 1) / 2; ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 1 ` ` ` `count_1 = count_1 + (i - prev - 1) / 2; ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev and current are 1 ` ` ` `else` `if` `(S[prev] == ` `'1'` `&& S[i] == ` `'1'` `) { ` ` ` ` ` `// All * will get converted to 1 ` ` ` `count_1 = count_1 + (i - prev - 1); ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// No * can be replaced ` ` ` `// by either 0 or 1 ` ` ` `else` `if` `(S[prev] == ` `'0'` `&& S[i] == ` `'1'` `) ` ` ` ` ` `// Prev becomes the ith character ` ` ` `prev = i; ` ` ` ` ` `// Check if prev and current are 0 ` ` ` `else` `if` `(S[prev] == ` `'0'` `&& S[i] == ` `'0'` `) { ` ` ` ` ` `// All * will get converted to 0 ` ` ` `count_0 = count_0 + (i - prev - 1); ` ` ` `prev = i; ` ` ` `} ` ` ` `} ` ` ` ` ` `// If frequency of 0 ` ` ` `// is more ` ` ` `if` `(count_0 > count_1) ` ` ` `cout << ` `"0"` `; ` ` ` ` ` `// If frequency of 1 ` ` ` `// is more ` ` ` `else` `if` `(count_1 > count_0) ` ` ` `cout << ` `"1"` `; ` ` ` ` ` `else` `{ ` ` ` `cout << -1; ` ` ` `} ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `// Given string ` ` ` `string str = ` `"**0**1***0"` `; ` ` ` ` ` `// Function Call ` ` ` `solve(str); ` ` ` ` ` `return` `0; ` `} ` |

## Java

`// Java program for the above approach ` `import` `java.io.*; ` ` ` `class` `GFG{ ` ` ` `// Function to find the ` `// maximum occurring character ` `static` `void` `solve(String S) ` `{ ` ` ` ` ` `// Initialize count of ` ` ` `// zero and one ` ` ` `int` `count_0 = ` `0` `, count_1 = ` `0` `; ` ` ` ` ` `int` `prev = -` `1` `; ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = ` `0` `; i < S.length(); i++) ` ` ` `{ ` ` ` ` ` `// Count the zeros ` ` ` `if` `(S.charAt(i) == ` `'0'` `) ` ` ` `count_0++; ` ` ` ` ` `// Count the ones ` ` ` `else` `if` `(S.charAt(i) == ` `'1'` `) ` ` ` `count_1++; ` ` ` `} ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = ` `0` `; i < S.length(); i++) ` ` ` `{ ` ` ` ` ` `// Check if character ` ` ` `// is * then continue ` ` ` `if` `(S.charAt(i) == ` `'*'` `) ` ` ` `continue` `; ` ` ` ` ` `// Check if first character ` ` ` `// after * is X ` ` ` `else` `if` `(S.charAt(i) == ` `'0'` `&& prev == -` `1` `) ` ` ` `{ ` ` ` ` ` `// Add all * to ` ` ` `// the frequency of X ` ` ` `count_0 = count_0 + i; ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if first character ` ` ` `// after * is Y ` ` ` `else` `if` `(S.charAt(i) == ` `'1'` `&& prev == -` `1` `) ` ` ` `{ ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev character is 1 ` ` ` `// and current character is 0 ` ` ` `else` `if` `(S.charAt(prev) == ` `'1'` `&& ` ` ` `S.charAt(i) == ` `'0'` `) ` ` ` `{ ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 0 ` ` ` `count_0 = count_0 + (i - prev - ` `1` `) / ` `2` `; ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 1 ` ` ` `count_1 = count_1 + (i - prev - ` `1` `) / ` `2` `; ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev and current are 1 ` ` ` `else` `if` `(S.charAt(prev) == ` `'1'` `&& ` ` ` `S.charAt(i) == ` `'1'` `) ` ` ` `{ ` ` ` ` ` `// All * will get converted to 1 ` ` ` `count_1 = count_1 + (i - prev - ` `1` `); ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// No * can be replaced ` ` ` `// by either 0 or 1 ` ` ` `else` `if` `(S.charAt(prev) == ` `'0'` `&& ` ` ` `S.charAt(i) == ` `'1'` `) ` ` ` ` ` `// Prev becomes the ith character ` ` ` `prev = i; ` ` ` ` ` `// Check if prev and current are 0 ` ` ` `else` `if` `(S.charAt(prev) == ` `'0'` `&& ` ` ` `S.charAt(i) == ` `'0'` `) ` ` ` `{ ` ` ` ` ` `// All * will get converted to 0 ` ` ` `count_0 = count_0 + (i - prev - ` `1` `); ` ` ` `prev = i; ` ` ` `} ` ` ` `} ` ` ` ` ` `// If frequency of 0 ` ` ` `// is more ` ` ` `if` `(count_0 > count_1) ` ` ` `System.out.print(` `"0"` `); ` ` ` ` ` `// If frequency of 1 ` ` ` `// is more ` ` ` `else` `if` `(count_1 > count_0) ` ` ` `System.out.print(` `"1"` `); ` ` ` ` ` `else` ` ` `{ ` ` ` `System.out.print(` `"-1"` `); ` ` ` `} ` `} ` ` ` `// Driver code ` `public` `static` `void` `main (String[] args) ` `{ ` ` ` ` ` `// Given string ` ` ` `String str = ` `"**0**1***0"` `; ` ` ` ` ` `// Function call ` ` ` `solve(str); ` `} ` `} ` ` ` `// This code is contributed by code_hunt ` |

## Python3

`# Python3 program for the above approach ` ` ` `# Function to find the ` `# maximum occurring character ` `def` `solve(S): ` ` ` ` ` `# Initialize count of ` ` ` `# zero and one ` ` ` `count_0 ` `=` `0` ` ` `count_1 ` `=` `0` ` ` ` ` `prev ` `=` `-` `1` ` ` ` ` `# Iterate over the given string ` ` ` `for` `i ` `in` `range` `(` `len` `(S)) : ` ` ` ` ` `# Count the zeros ` ` ` `if` `(S[i] ` `=` `=` `'0'` `): ` ` ` `count_0 ` `+` `=` `1` ` ` ` ` `# Count the ones ` ` ` `elif` `(S[i] ` `=` `=` `'1'` `): ` ` ` `count_1 ` `+` `=` `1` ` ` ` ` `# Iterate over the given string ` ` ` `for` `i ` `in` `range` `(` `len` `(S)): ` ` ` ` ` `# Check if character ` ` ` `# is * then continue ` ` ` `if` `(S[i] ` `=` `=` `'*'` `): ` ` ` `continue` ` ` ` ` `# Check if first character ` ` ` `# after * is X ` ` ` `elif` `(S[i] ` `=` `=` `'0'` `and` `prev ` `=` `=` `-` `1` `): ` ` ` ` ` `# Add all * to ` ` ` `# the frequency of X ` ` ` `count_0 ` `=` `count_0 ` `+` `i ` ` ` ` ` `# Set prev to the ` ` ` `# i-th character ` ` ` `prev ` `=` `i ` ` ` ` ` `# Check if first character ` ` ` `# after * is Y ` ` ` `elif` `(S[i] ` `=` `=` `'1'` `and` `prev ` `=` `=` `-` `1` `): ` ` ` ` ` `# Set prev to the ` ` ` `# i-th character ` ` ` `prev ` `=` `i ` ` ` ` ` `# Check if prev character is 1 ` ` ` `# and current character is 0 ` ` ` `elif` `(S[prev] ` `=` `=` `'1'` `and` `S[i] ` `=` `=` `'0'` `): ` ` ` ` ` `# Half of the * will be ` ` ` `# converted to 0 ` ` ` `count_0 ` `=` `count_0 ` `+` `(i ` `-` `prev ` `-` `1` `) ` `/` `2` ` ` ` ` `# Half of the * will be ` ` ` `# converted to 1 ` ` ` `count_1 ` `=` `count_1 ` `+` `(i ` `-` `prev ` `-` `1` `) ` `/` `/` `2` ` ` `prev ` `=` `i ` ` ` ` ` `# Check if prev and current are 1 ` ` ` `elif` `(S[prev] ` `=` `=` `'1'` `and` `S[i] ` `=` `=` `'1'` `): ` ` ` ` ` `# All * will get converted to 1 ` ` ` `count_1 ` `=` `count_1 ` `+` `(i ` `-` `prev ` `-` `1` `) ` ` ` `prev ` `=` `i ` ` ` ` ` `# No * can be replaced ` ` ` `# by either 0 or 1 ` ` ` `elif` `(S[prev] ` `=` `=` `'0'` `and` `S[i] ` `=` `=` `'1'` `): ` ` ` ` ` `# Prev becomes the ith character ` ` ` `prev ` `=` `i ` ` ` ` ` `# Check if prev and current are 0 ` ` ` `elif` `(S[prev] ` `=` `=` `'0'` `and` `S[i] ` `=` `=` `'0'` `): ` ` ` ` ` `# All * will get converted to 0 ` ` ` `count_0 ` `=` `count_0 ` `+` `(i ` `-` `prev ` `-` `1` `) ` ` ` `prev ` `=` `i ` ` ` ` ` `# If frequency of 0 ` ` ` `# is more ` ` ` `if` `(count_0 > count_1): ` ` ` `print` `(` `"0"` `) ` ` ` ` ` `# If frequency of 1 ` ` ` `# is more ` ` ` `elif` `(count_1 > count_0): ` ` ` `print` `(` `"1"` `) ` ` ` `else` `: ` ` ` `print` `(` `"-1"` `) ` ` ` `# Driver code ` ` ` `# Given string ` `str` `=` `"**0**1***0"` ` ` `# Function call ` `solve(` `str` `) ` ` ` `# This code is contributed by code_hunt` |

## C#

`// C# program for the above approach ` `using` `System; ` ` ` `class` `GFG{ ` ` ` `// Function to find the ` `// maximum occurring character ` `static` `void` `solve(` `string` `S) ` `{ ` ` ` ` ` `// Initialize count of ` ` ` `// zero and one ` ` ` `int` `count_0 = 0, count_1 = 0; ` ` ` ` ` `int` `prev = -1; ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = 0; i < S.Length; i++) ` ` ` `{ ` ` ` ` ` `// Count the zeros ` ` ` `if` `(S[i] == ` `'0'` `) ` ` ` `count_0++; ` ` ` ` ` `// Count the ones ` ` ` `else` `if` `(S[i] == ` `'1'` `) ` ` ` `count_1++; ` ` ` `} ` ` ` ` ` `// Iterate over the given string ` ` ` `for` `(` `int` `i = 0; i < S.Length; i++) ` ` ` `{ ` ` ` ` ` `// Check if character ` ` ` `// is * then continue ` ` ` `if` `(S[i] == ` `'*'` `) ` ` ` `continue` `; ` ` ` ` ` `// Check if first character ` ` ` `// after * is X ` ` ` `else` `if` `(S[i] == ` `'0'` `&& prev == -1) ` ` ` `{ ` ` ` ` ` `// Add all * to ` ` ` `// the frequency of X ` ` ` `count_0 = count_0 + i; ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if first character ` ` ` `// after * is Y ` ` ` `else` `if` `(S[i] == ` `'1'` `&& prev == -1) ` ` ` `{ ` ` ` ` ` `// Set prev to the ` ` ` `// i-th character ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev character is 1 ` ` ` `// and current character is 0 ` ` ` `else` `if` `(S[prev] == ` `'1'` `&& S[i] == ` `'0'` `) ` ` ` `{ ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 0 ` ` ` `count_0 = count_0 + (i - prev - 1) / 2; ` ` ` ` ` `// Half of the * will be ` ` ` `// converted to 1 ` ` ` `count_1 = count_1 + (i - prev - 1) / 2; ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// Check if prev and current are 1 ` ` ` `else` `if` `(S[prev] == ` `'1'` `&& S[i] == ` `'1'` `) ` ` ` `{ ` ` ` ` ` `// All * will get converted to 1 ` ` ` `count_1 = count_1 + (i - prev - 1); ` ` ` `prev = i; ` ` ` `} ` ` ` ` ` `// No * can be replaced ` ` ` `// by either 0 or 1 ` ` ` `else` `if` `(S[prev] == ` `'0'` `&& S[i] == ` `'1'` `) ` ` ` ` ` `// Prev becomes the ith character ` ` ` `prev = i; ` ` ` ` ` `// Check if prev and current are 0 ` ` ` `else` `if` `(S[prev] == ` `'0'` `&& S[i] == ` `'0'` `) ` ` ` `{ ` ` ` ` ` `// All * will get converted to 0 ` ` ` `count_0 = count_0 + (i - prev - 1); ` ` ` `prev = i; ` ` ` `} ` ` ` `} ` ` ` ` ` `// If frequency of 0 ` ` ` `// is more ` ` ` `if` `(count_0 > count_1) ` ` ` `Console.Write(` `"0"` `); ` ` ` ` ` `// If frequency of 1 ` ` ` `// is more ` ` ` `else` `if` `(count_1 > count_0) ` ` ` `Console.Write(` `"1"` `); ` ` ` ` ` `else` ` ` `{ ` ` ` `Console.Write(` `"-1"` `); ` ` ` `} ` `} ` ` ` `// Driver code ` `public` `static` `void` `Main () ` `{ ` ` ` ` ` `// Given string ` ` ` `string` `str = ` `"**0**1***0"` `; ` ` ` ` ` `// Function call ` ` ` `solve(str); ` `} ` `} ` ` ` `// This code is contributed by code_hunt ` |

**Output:**

0

**Time Complexity: **O(N) **Auxiliary Space: **O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.