Minimice la cantidad de reemplazos para obtener una string con la misma cantidad de ‘a’, ‘b’ y ‘c’ en ella

Posted on by Rudeus Greyrat

Dada una string que consta de solo tres posibles caracteres ‘a’, ‘b’ o ‘c’. La tarea es reemplazar los caracteres de la string dada con ‘a’, ‘b’ o ‘c’ solo de modo que haya el mismo número de caracteres de ‘a’, ‘b’ y ‘c’ en la string. La tarea es minimizar el número de reemplazos e imprimir la string lexicográficamente más pequeña posible de todas esas strings con los reemplazos mínimos.

Si no es posible obtener tal string, imprima -1.

Ejemplos:

Input : s = "bcabba"
Output : bcabca
Number of replacements done is 1 and this is
the lexicographically smallest possible 

Input : "aaaaaa"
Output : aabbcc

Input : "aaaaa"
Output : -1

Acercarse:

  • Cuente el número de ‘a’, ‘b’ y ‘c’ en la string.
  • Si el conteo de ellos es igual, entonces la misma string será la respuesta.
  • Si la longitud de la string no es un múltiplo de 3, entonces no es posible.
  • Primero, reduzca el número de a en exceso en la string.
    1. Reemplace ‘c’ por ‘a’ si hay ‘c’ adicionales utilizando una técnica de ventana deslizante desde la izquierda.
    2. Reemplace ‘b’ por ‘a’ si hay ‘b’ adicionales utilizando una técnica de ventana deslizante desde la izquierda en caso de que no haya ‘c’ en un índice.
  • En segundo lugar, reduzca el número de b en exceso en la string reemplazando ‘c’ desde el frente usando la ventana deslizante.
  • En tercer lugar, reduzca el número de c en exceso al reducir el número de ‘a’ adicionales desde la parte posterior usando la ventana deslizante.
  • En cuarto lugar, reduzca el número de b en exceso en la string reduciendo el número de ‘a’ adicionales desde atrás.
  • En quinto lugar, reduzca el número de c en exceso, si las hay, reduciendo el número de ‘b’ adicionales desde atrás.

Seguimos reemplazando desde atrás para obtener la string lexicográficamente más pequeña.

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

C++

// CPP program to Minimize the number of
// replacements to get a string with same
// number of ‘a’, ‘b’ and ‘c’ in it
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to count numbers
string lexoSmallest(string s, int n)
{
    // Count the number of 'a', 'b' and
    // 'c' in string
    int ca = 0, cb = 0, cc = 0;
  
    for (int i = 0; i < n; i++) {
        if (s[i] == 'a')
            ca++;
        else if (s[i] == 'b')
            cb++;
        else
            cc++;
    }
  
    // If equal previously
    if (ca == cb && cb == cc) {
        return s;
    }
  
    int cnt = n / 3;
  
    // If not a multiple of 3
    if (cnt * 3 != n) {
        return "-1";
    }
  
    int i = 0;
  
    // Increase the number of a's by
    // removing extra 'b' and ;c;
    while (ca < cnt && i < n) {
  
        // Check if it is 'b' and it more
        // than n/3
        if (s[i] == 'b' && cb > cnt) {
            cb--;
            s[i] = 'a';
            ca++;
        }
  
        // Check if it is 'c' and it
        // more than n/3
        else if (s[i] == 'c' && cc > cnt) {
            cc--;
            s[i] = 'a';
            ca++;
        }
  
        i++;
    }
  
    i = 0;
  
    // Increase the number of b's by
    // removing extra 'c'
    while (cb < cnt && i < n) {
  
        // Check if it is 'c' and it more
        // than n/3
        if (s[i] == 'c' && cc > cnt) {
            cc--;
            s[i] = '1';
  
            cb++;
        }
        i++;
    }
  
    i = n - 1;
  
    // Increase the number of c's from back
    while (cc < cnt && i >= 0) {
  
        // Check if it is 'a' and it more
        // than n/3
        if (s[i] == 'a' && ca > cnt) {
            ca--;
            s[i] = 'c';
            cc++;
        }
  
        i--;
    }
  
    i = n - 1;
  
    // Increase the number of b's from back
    while (cb < cnt && i >= 0) {
  
        // Check if it is 'a' and it more
        // than n/3
        if (s[i] == 'a' && ca > cnt) {
            ca--;
            s[i] = 'b';
            cb++;
        }
  
        i--;
    }
  
    i = n - 1;
  
    // Increase the number of c's from back
    while (cc < cnt && i >= 0) {
  
        // Check if it is 'b' and it more
        // than n/3
        if (s[i] == 'b' && cb > cnt) {
            cb--;
            s[i] = 'c';
            cc++;
        }
  
        i--;
    }
  
    return s;
}
  
// Driver Code
int main()
{
    string s = "aaaaaa";
    int n = s.size();
  
    cout << lexoSmallest(s, n);
  
    return 0;
}

Python3

# Python3 program to Minimize the number of
# replacements to get a string with same
# number of 'a', 'b' and 'c' in it
  
# Function to count numbers
def lexoSmallest(s, n):
      
    # Count the number of 'a', 'b' and
    # 'c' in string
    ca = 0
    cb = 0
    cc = 0
    for i in range(n):
        if (s[i] == 'a'):
            ca += 1
        elif (s[i] == 'b'):
            cb += 1
        else:
            cc += 1
      
    # If equal previously
    if (ca == cb and cb == cc):
        return s
          
    cnt = n // 3
      
    # If not a multiple of 3
    if (cnt * 3 != n):
        return "-1"
          
    i = 0
      
    # Increase the number of a's by
    # removing extra 'b' and c
    while (ca < cnt and i < n):
          
        # Check if it is 'b' and it more
        # than n/3
        if (s[i] == 'b' and cb > cnt) :
            cb -= 1
            s[i] = 'a'
            ca += 1
              
        # Check if it is 'c' and it
        # more than n/3
        elif (s[i] == 'c' and cc > cnt):
            cc -= 1
            s[i] = 'a'
            ca += 1
              
        i += 1
    i = 0
      
    # Increase the number of b's by
    # removing extra 'c'
    while (cb < cnt and i < n):
          
        # Check if it is 'c' and it more
        # than n/3
        if (s[i] == 'c' and cc > cnt):
            cc -= 1
            s[i] = '1'
            cb += 1
          
        i += 1
      
    i = n - 1
      
    # Increase the number of c's from back
    while (cc < cnt and i >= 0):
          
        # Check if it is 'a' and it more
        # than n/3
        if (s[i] == 'a' and ca > cnt):
            ca -= 1
            s[i] = 'c'
            cc += 1
          
        i -= 1
      
    i = n - 1
      
    # Increase the number of b's from back
    while (cb < cnt and i >= 0):
         
        # Check if it is 'a' and it more
        # than n/3
        if (s[i] == 'a' and ca > cnt):
            ca -= 1
            s[i] = 'b'
            cb += 1
              
        i -= 1
          
    i = n - 1
      
    # Increase the number of c's from back
    while (cc < cnt and i >= 0):
          
        # Check if it is 'b' and it more
        # than n/3
        if (s[i] == 'b' and cb > cnt):
            cb -= 1
            s[i] = 'c'
            cc += 1
          
        i -= 1
    return s
  
# Driver Code
  
s = "aaaaaa"
n = len(s)
  
print(*lexoSmallest(list(s), n),sep="")
  
# This code is contributed by shivanisinghss2110

C#

// C# program to minimize the number of
// replacements to get a string with same
// number of ‘a’, ‘b’ and ‘c’ in it
using System;
using System.Text; 
  
class GFG{
      
// Function to count numbers
static string lexoSmallest(string str, int n)
{
      
    // Count the number of 'a', 'b' and
    // 'c' in string
    int ca = 0, cb = 0, cc = 0;
    StringBuilder s = new StringBuilder(str); 
  
    for(int j = 0; j < n; j++)
    {
        if (s[j] == 'a')
            ca++;
        else if (s[j] == 'b')
            cb++;
        else
            cc++;
    }
  
    // If equal previously
    if (ca == cb && cb == cc) 
    {
        return s.ToString();
    }
  
    int cnt = n / 3;
  
    // If not a multiple of 3
    if (cnt * 3 != n)
    {
        return "-1";
    }
  
    int i = 0;
  
    // Increase the number of a's by
    // removing extra 'b' and ;c;
    while (ca < cnt && i < n)
    {
          
        // Check if it is 'b' and it more
        // than n/3
        if (s[i] == 'b' && cb > cnt)
        {
            cb--;
            s[i] = 'a';
            ca++;
        }
  
        // Check if it is 'c' and it
        // more than n/3
        else if (s[i] == 'c' && cc > cnt)
        {
            cc--;
            s[i] = 'a';
            ca++;
        }
        i++;
    }
  
    i = 0;
  
    // Increase the number of b's by
    // removing extra 'c'
    while (cb < cnt && i < n)
    {
          
        // Check if it is 'c' and it more
        // than n/3
        if (s[i] == 'c' && cc > cnt) 
        {
            cc--;
            s[i] = '1';
  
            cb++;
        }
        i++;
    }
  
    i = n - 1;
  
    // Increase the number of c's from back
    while (cc < cnt && i >= 0) 
    {
          
        // Check if it is 'a' and it more
        // than n/3
        if (s[i] == 'a' && ca > cnt)
        {
            ca--;
            s[i] = 'c';
            cc++;
        }
        i--;
    }
  
    i = n - 1;
  
    // Increase the number of b's from back
    while (cb < cnt && i >= 0)
    {
          
        // Check if it is 'a' and it more
        // than n/3
        if (s[i] == 'a' && ca > cnt)
        {
            ca--;
            s[i] = 'b';
            cb++;
        }
        i--;
    }
  
    i = n - 1;
  
    // Increase the number of c's from back
    while (cc < cnt && i >= 0)
    {
          
        // Check if it is 'b' and it more
        // than n/3
        if (s[i] == 'b' && cb > cnt) 
        {
            cb--;
            s[i] = 'c';
            cc++;
        }
        i--;
    }
    return s.ToString();
} 
      
// Driver Code
public static void Main(string[] args)
{
    string s = "aaaaaa";
    int n = s.Length;
      
    Console.Write(lexoSmallest(s, n));
}
}
  
// This code is contributed by rutvik_56

PHP

<?php
// PHP program to Minimize the number of 
// replacements to get a string with same 
// number of ‘a’, ‘b’ and ‘c’ in it 
  
// Function to count numbers 
function lexoSmallest($s, $n) 
{ 
    // Count the number of 'a', 'b' 
    // and 'c' in string 
    $ca = 0;
    $cb = 0;
    $cc = 0; 
  
    for ($i = 0; $i < $n; $i++) 
    { 
        if ($s[$i] == 'a') 
            $ca++; 
        else if ($s[$i] == 'b') 
            $cb++; 
        else
            $cc++; 
    } 
  
    // If equal previously 
    if ($ca == $cb && $cb == $cc)
    { 
        return $s; 
    } 
  
    $cnt = floor($n / 3); 
  
    // If not a multiple of 3 
    if ($cnt * 3 != $n) 
    { 
        return "-1"; 
    } 
  
    $i = 0; 
  
    // Increase the number of a's by 
    // removing extra 'b' and ;c; 
    while ($ca < $cnt && $i < $n) 
    { 
  
        // Check if it is 'b' and it is
        // more than n/3 
        if ($s[$i] == 'b' && $cb > $cnt) 
        { 
            $cb--; 
            $s[$i] = 'a'; 
            $ca++; 
        } 
  
        // Check if it is 'c' and it 
        // more than n/3 
        else if ($s[$i] == 'c' && $cc > $cnt) 
        { 
            $cc--; 
            $s[$i] = 'a'; 
            $ca++; 
        } 
  
        $i++; 
    } 
  
    $i = 0; 
  
    // Increase the number of b's by 
    // removing extra 'c' 
    while ($cb < $cnt && $i < $n) 
    { 
  
        // Check if it is 'c' and it more 
        // than n/3 
        if ($s[$i] == 'c' && $cc > $cnt) 
        { 
            $cc--; 
            $s[$i] = '1'; 
  
            $cb++; 
        } 
        $i++; 
    } 
  
    $i = $n - 1; 
  
    // Increase the number of c's from back 
    while ($cc < $cnt && $i >= 0) 
    { 
  
        // Check if it is 'a' and it is 
        // more than n/3 
        if ($s[$i] == 'a' && $ca > $cnt) 
        { 
            $ca--; 
            $s[$i] = 'c'; 
            $cc++; 
        } 
  
        $i--; 
    } 
  
    $i = $n - 1; 
  
    // Increase the number of b's from back 
    while ($cb < $cnt && $i >= 0) 
    { 
  
        // Check if it is 'a' and it is 
        // more than n/3 
        if ($s[$i] == 'a' && $ca > $cnt) 
        { 
            $ca--; 
            $s[$i] = 'b'; 
            $cb++; 
        } 
  
        $i--; 
    } 
  
    $i = $n - 1; 
  
    // Increase the number of c's from back 
    while ($cc < $cnt && $i >= 0) 
    { 
  
        // Check if it is 'b' and it more 
        // than n/3 
        if ($s[$i] == 'b' && $cb > $cnt) 
        { 
            $cb--; 
            $s[$i] = 'c'; 
            $cc++; 
        } 
  
        $i--; 
    } 
  
    return $s; 
} 
  
// Driver Code 
$s = "aaaaaa"; 
$n = strlen($s); 
  
echo lexoSmallest($s, $n);
  
// This code is contributed by Ryuga.
?>
  

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *