Dada una string str que contiene solo los caracteres 0 , 1 y 2 , puede intercambiar dos caracteres adyacentes (consecutivos) 0 y 1 o dos caracteres adyacentes (consecutivos) 1 y 2 . La tarea es obtener la string mínima posible (lexicográficamente) usando estos intercambios un número arbitrario de veces.
Ejemplos:
Entrada: str = «100210»
Salida: 001120
Podemos intercambiar 0 y 1 O podemos intercambiar 1 y 2. No se permite intercambiar 0 y 2. Todos los intercambios pueden ocurrir solo para adyacentes.
Entrada: str = «2021»
Salida: 1202
Tenga en cuenta que 0 y 2 no se pueden intercambiar
Enfoque: puede imprimir todos los 1 juntos, ya que 1 se puede intercambiar con cualquiera de los otros caracteres, mientras que 0 y 2 no se pueden intercambiar, por lo que todos los 0 y 2 seguirán el mismo orden que la string original.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the required string
void printString(string str, int n)
{
// count number of 1s
int ones = 0;
for (int i = 0; i < n; i++)
if (str[i] == '1')
ones++;
// To check if the all the 1s
// have been used or not
bool used = false;
for (int i = 0; i < n; i++) {
if (str[i] == '2' && !used) {
used = 1;
// Print all the 1s if any 2 is encountered
for (int j = 0; j < ones; j++)
cout << "1";
}
// If str[i] = 0 or str[i] = 2
if (str[i] != '1')
cout << str[i];
}
// If 1s are not printed yet
if (!used)
for (int j = 0; j < ones; j++)
cout << "1";
}
// Driver code
int main()
{
string str = "100210";
int n = str.length();
printString(str, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to print the required string
static void printString(char[] str, int n)
{
// count number of 1s
int ones = 0;
for (int i = 0; i < n; i++)
if (str[i] == '1')
ones++;
// To check if the all the 1s
// have been used or not
boolean used = false;
for (int i = 0; i < n; i++)
{
if (str[i] == '2' && !used)
{
used = true;
// Print all the 1s if any 2 is encountered
for (int j = 0; j < ones; j++)
System.out.print("1");
}
// If str[i] = 0 or str[i] = 2
if (str[i] != '1')
System.out.print(str[i]);
}
// If 1s are not printed yet
if (!used)
for (int j = 0; j < ones; j++)
System.out.print("1");
}
// Driver code
public static void main(String[] args)
{
String str = "100210";
int n = str.length();
printString(str.toCharArray(), n);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
# Function to print the required string
def printString(Str1, n):
# count number of 1s
ones = 0
for i in range(n):
if (Str1[i] == '1'):
ones += 1
# To check if the all the 1s
# have been used or not
used = False
for i in range(n):
if (Str1[i] == '2' and used == False):
used = 1
# Print all the 1s if any 2 is encountered
for j in range(ones):
print("1", end = "")
# If Str1[i] = 0 or Str1[i] = 2
if (Str1[i] != '1'):
print(Str1[i], end = "")
# If 1s are not printed yet
if (used == False):
for j in range(ones):
print("1", end = "")
# Driver code
Str1 = "100210"
n = len(Str1)
printString(Str1, n)
# This code is contributed
# by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the required string
static void printString(char[] str, int n)
{
// count number of 1s
int ones = 0;
for (int i = 0; i < n; i++)
if (str[i] == '1')
ones++;
// To check if the all the 1s
// have been used or not
bool used = false;
for (int i = 0; i < n; i++)
{
if (str[i] == '2' && !used)
{
used = true;
// Print all the 1s if any 2 is encountered
for (int j = 0; j < ones; j++)
Console.Write("1");
}
// If str[i] = 0 or str[i] = 2
if (str[i] != '1')
Console.Write(str[i]);
}
// If 1s are not printed yet
if (!used)
for (int j = 0; j < ones; j++)
Console.Write("1");
}
// Driver code
public static void Main(String[] args)
{
String str = "100210";
int n = str.Length;
printString(str.ToCharArray(), n);
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
// Function to print the required string
function printString($str, $n)
{
// count number of 1s
$ones = 0;
for ($i = 0; $i < $n; $i++)
if ($str[$i] == '1')
$ones++;
// To check if the all the 1s
// have been used or not
$used = false;
for ($i = 0; $i < $n; $i++)
{
if ($str[$i] == '2' && !$used)
{
$used = 1;
// Print all the 1s if any 2
// is encountered
for ($j = 0; $j < $ones; $j++)
echo "1";
}
// If str[i] = 0 or str[i] = 2
if ($str[$i] != '1')
echo $str[$i];
}
// If 1s are not printed yet
if (!$used)
for ($j = 0; $j < $ones; $j++)
echo "1";
}
// Driver code
$str = "100210";
$n = strlen($str);
printString($str, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to print the required string
function printString(str, n)
{
// count number of 1s
let ones = 0;
for (let i = 0; i < n; i++)
if (str[i] == '1')
ones++;
// To check if the all the 1s
// have been used or not
let used = false;
for (let i = 0; i < n; i++)
{
if (str[i] == '2' && !used)
{
used = true;
// Print all the 1s if any 2 is encountered
for (let j = 0; j < ones; j++)
document.write("1");
}
// If str[i] = 0 or str[i] = 2
if (str[i] != '1')
document.write(str[i]);
}
// If 1s are not printed yet
if (!used)
for (let j = 0; j < ones; j++)
document.write("1");
}
let str = "100210";
let n = str.length;
printString(str.split(''), n);
</script>
Producción:
001120
Publicación traducida automáticamente
Artículo escrito por Bhashkar_P y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA