Maximice las eliminaciones de caracteres minoritarios que se pueden realizar a partir de una substring de string binaria dada

Python

Dada la string binaria str de tamaño, N . Seleccione cualquier substring de la string y elimine todas las apariciones del carácter minoritario (es decir, el carácter que tiene menos frecuencia) de la substring. La tarea es averiguar el número máximo de caracteres que se pueden eliminar al realizar una de esas operaciones.

Nota: si alguna substring tiene tanto ‘0’ como ‘1’ en los mismos números, no se puede eliminar ningún carácter.

Ejemplos:

Entrada: str = “01”
Salida: 0
Explicación: No se puede eliminar ningún carácter.
Las substrings son «0», «1» y «01».
Para «0», el carácter minoritario es ‘1’ y no es posible eliminarlo de esta substring ya que aquí no hay ‘1’.
Lo mismo para la substring «1». Y la substring «01» no tiene ningún elemento minoritario.
Las apariciones de ‘1’ y ‘0’ son las mismas en la substring «01».

Entrada: str = «00110001000»
Salida: 3
Explicación: elimine todos los 1 de la substring «1100010».

Enfoque: Los siguientes son los casos para las supresiones máximas posibles

• Caso-1: Cuando se pueden eliminar todos los 0 o 1 . Cuando el recuento total de ‘0’ y ‘ 1′ no sea el mismo, seleccione la string completa y elimine todas las apariciones del elemento minoritario.
• Caso-2: Cuando ambos personajes están en el mismo número. Aquí, al elegir la string completa, no podrá eliminar ningún carácter. Entonces, tome una substring de tal manera que el conteo de uno de los caracteres sea el mismo que su conteo en la string real y para el otro sea uno menos. Entonces, las posibles eliminaciones son (recuento de cualquier carácter en la string completa – 1) .
• Caso-3: Cuando la string contiene solo un tipo de carácter. Entonces no es posible la eliminación.

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum number of removals
int maxRem(string str)
{
    // Map to store count of zeroes and ones
    map<char, int> mp;
    for (auto& value : str)
        mp[value]++;
 
    // If the count of both characters are same
    // then longest substring is the whole string
    // except the last character
    if (mp['0'] == mp['1']) {
        return (mp['0'] - 1);
    }
 
    // If the count of both characters
    // are unequal so the largest substring
    // is whole string and ans is
    // the minimum count of a character
    else
        return min(mp['0'], mp['1']);
}
 
// Driver code
int main()
{
    string str = "00110001000";
 
    int ans = maxRem(str);
    cout << ans;
    return 0;
}

// Java program to implement the approach
import java.util.*;
class GFG{
 
  // Function to find maximum number of removals
  static int maxRem(String str)
  {
     
    // Map to store count of zeroes and ones
    HashMap<Character,Integer> mp = new HashMap<Character,Integer>();
    for (char value : str.toCharArray())
      if(mp.containsKey(value))
        mp.put(value, mp.get(value)+1);
    else
      mp.put(value, 1);
 
    // If the count of both characters are same
    // then longest subString is the whole String
    // except the last character
    if (mp.get('0') == mp.get('1')) {
      return (mp.get('0') - 1);
    }
 
    // If the count of both characters
    // are unequal so the largest subString
    // is whole String and ans is
    // the minimum count of a character
    else
      return Math.min(mp.get('0'), mp.get('1'));
  }
 
  // Driver code
  public static void main(String[] args)
  {
    String str = "00110001000";
 
    int ans = maxRem(str);
    System.out.print(ans);
  }
}
 
// This code is contributed by shikhasingrajput

# Python program to implement the approach
# Function to find maximum number of removals
def maxRem(s, n):
 
    # Map to store count of zeroes and ones
    mp = {}
 
    for i in range(0, n):
        if(not mp.__contains__(s[i])):
            mp[s[i]] = 1
        else:
            mp[s[i]] += 1
 
    # If the count of both characters are same
    # then longest substring is the whole string
    # except the last character
    if(mp['0'] == mp['1']):
        return (mp['0'] - 1)
 
    # If the count of both characters
    # are unequal so the largest substring
    # is whole string and ans is
    # the minimum count of a character
    else:
        return min(mp['0'], mp['1'])
 
# Driver code
 
s = "00110001000"
n = len(s)
ans = maxRem(s, n)
print(ans)
 
# This code is contributed by Palak Gupta

// C# program to implement the approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find maximum number of removals
  static int maxRem(string str)
  {
 
    // Map to store count of zeroes and ones
    Dictionary<char, int> mp =
      new Dictionary<char, int>();
 
    for (int i = 0; i < str.Length; i++) {
      if(!mp.ContainsKey(str[i])) {
        mp.Add(str[i], 1);
      }
      else {
        mp[str[i]] = mp[str[i]] + 1;
      }
    }
 
    // If the count of both characters are same
    // then longest substring is the whole string
    // except the last character
    if (mp['0'] == mp['1']) {
      return (mp['0'] - 1);
    }
 
    // If the count of both characters
    // are unequal so the largest substring
    // is whole string and ans is
    // the minimum count of a character
    else {
      return Math.Min(mp['0'], mp['1']);
    }
  }
 
  // Driver code
  public static void Main()
  {
    string str = "00110001000";
 
    int ans = maxRem(str);
    Console.Write(ans);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to find maximum number of removals
       function maxRem(str)
       {
        
           // Map to store count of zeroes and ones
           let mp = new Map();
           for (let i = 0; i < str.length; i++) {
               if (mp.has(str[i])) {
                   mp.set(str[i], mp.get(str[i]) + 1)
               }
               else {
                   mp.set(str[i], 1)
               }
           }
 
           // If the count of both characters are same
           // then longest substring is the whole string
           // except the last character
           if (mp.get('0') == mp.get('1')) {
               return (mp.get('0') - 1);
           }
 
           // If the count of both characters
           // are unequal so the largest substring
           // is whole string and ans is
           // the minimum count of a character
           else
               return Math.min(mp.get('0'), mp.get('1'));
       }
 
       // Driver code
       let str = "00110001000";
 
       let ans = maxRem(str);
       document.write(ans);
 
      // This code is contributed by Potta Lokesh
   </script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)