String dada str de alfabetos ingleses en minúsculas. Uno puede elegir dos caracteres cualquiera en la string y reemplazar todas las ocurrencias del primer carácter con el segundo carácter y reemplazar todas las ocurrencias del segundo carácter con el primer carácter. Encuentre la string lexicográficamente más pequeña que se puede obtener haciendo esta operación como máximo una vez. Ejemplos:
Entrada: str = “ccad”
Salida: aacd
Intercambie todas las apariciones de ‘c’ con ‘a’ y todas las apariciones de ‘a’ con ‘c’ para obtener “aacd”, que es la string lexicográficamente más pequeña que podemos obtener.Entrada: str = “abba”
Salida: abba
La única operación posible convertirá la string dada a “baab”, que no es lexicográficamente la más pequeña.
Acercarse:
- Primero, almacenamos la primera aparición de cada carácter en una string en una array hash chk[] .
- Para encontrar la string lexicográficamente más pequeña, el carácter más a la izquierda debe reemplazarse con algún carácter que sea más pequeño que él. Esto solo sucederá si el carácter más pequeño aparece después de él en la array.
- Entonces, comience a recorrer la string desde la izquierda y para cada carácter, busque el carácter más pequeño (incluso más pequeño que el carácter actual) que aparece después de intercambiar todas sus ocurrencias para obtener la string requerida.
- Si no se encuentra tal par de caracteres en la string anterior, imprima la string dada ya que es la string más pequeña posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
#define MAX 26
// Function to return the lexicographically
// smallest string after swapping all the
// occurrences of any two characters
string smallestStr(string str, int n)
{
int i, j;
// To store the first index of
// every character of str
int chk[MAX];
for (i = 0; i < MAX; i++)
chk[i] = -1;
// Store the first occurring
// index every character
for (i = 0; i < n; i++) {
// If current character is appearing
// for the first time in str
if (chk[str[i] - 'a'] == -1)
chk[str[i] - 'a'] = i;
}
// Starting from the leftmost character
for (i = 0; i < n; i++) {
bool flag = false;
// For every character smaller than str[i]
for (j = 0; j < str[i] - 'a'; j++) {
// If there is a character in str which is
// smaller than str[i] and appears after it
if (chk[j] > chk[str[i] - 'a']) {
flag = true;
break;
}
}
// If the required character pair is found
if (flag)
break;
}
// If swapping is possible
if (i < n-1) {
// Characters to be swapped
char ch1 = str[i];
char ch2 = char(j + 'a');
// For every character
for (i = 0; i < n; i++) {
// Replace every ch1 with ch2
// and every ch2 with ch1
if (str[i] == ch1)
str[i] = ch2;
else if (str[i] == ch2)
str[i] = ch1;
}
}
return str;
}
// Driver code
int main()
{
string str = "ccad";
int n = str.length();
cout << smallestStr(str, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 26;
// Function to return the lexicographically
// smallest string after swapping all the
// occurrences of any two characters
static String smallestStr(char []str, int n)
{
int i, j = 0;
// To store the first index of
// every character of str
int []chk = new int[MAX];
for (i = 0; i < MAX; i++)
chk[i] = -1;
// Store the first occurring
// index every character
for (i = 0; i < n; i++)
{
// If current character is appearing
// for the first time in str
if (chk[str[i] - 'a'] == -1)
chk[str[i] - 'a'] = i;
}
// Starting from the leftmost character
for (i = 0; i < n; i++)
{
boolean flag = false;
// For every character smaller than str[i]
for (j = 0; j < str[i] - 'a'; j++)
{
// If there is a character in str which is
// smaller than str[i] and appears after it
if (chk[j] > chk[str[i] - 'a'])
{
flag = true;
break;
}
}
// If the required character pair is found
if (flag)
break;
}
// If swapping is possible
if (i < n-1)
{
// Characters to be swapped
char ch1 = str[i];
char ch2 = (char) (j + 'a');
// For every character
for (i = 0; i < n; i++)
{
// Replace every ch1 with ch2
// and every ch2 with ch1
if (str[i] == ch1)
str[i] = ch2;
else if (str[i] == ch2)
str[i] = ch1;
}
}
return String.valueOf(str);
}
// Driver code
public static void main(String[] args)
{
String str = "ccad";
int n = str.length();
System.out.println(smallestStr(
str.toCharArray(), n));
}
}
Python
# python3 implementation of the approach MAX=256 # Function to return the lexicographically # smallest after swapping all the # occurrences of any two characters def smallestStr(str, n): i, j=0,0 # To store the first index of # every character of str chk=[0 for i in range(MAX)] for i in range(MAX): chk[i] = -1 # Store the first occurring # index every character for i in range(n): # If current character is appearing # for the first time in str if (chk[ord(str[i])] == -1): chk[ord(str[i])] = i # Starting from the leftmost character for i in range(n): flag = False # For every character smaller than ord(str[i]) for j in range(ord(str[i])): # If there is a character in str which is # smaller than ord(str[i]) and appears after it if (chk[j] > chk[ord(str[i])]): flag = True break # If the required character pair is found if (flag): break # If swapping is possible if (i < n-1): # Characters to be swapped ch1 = (str[i]) ch2 = chr(j) # For every character for i in range(n): # Replace every ch1 with ch2 # and every ch2 with ch1 if (str[i] == ch1): str[i] = ch2 elif (str[i] == ch2): str[i] = ch1 return "".join(str) # Driver code st = "ccad" str=[i for i in st] n = len(str) print(smallestStr(str, n))
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 26;
// Function to return the lexicographically
// smallest string after swapping all the
// occurrences of any two characters
static String smallestStr(char []str, int n)
{
int i, j = 0;
// To store the first index of
// every character of str
int []chk = new int[MAX];
for (i = 0; i < MAX; i++)
chk[i] = -1;
// Store the first occurring
// index every character
for (i = 0; i < n; i++)
{
// If current character is appearing
// for the first time in str
if (chk[str[i] - 'a'] == -1)
chk[str[i] - 'a'] = i;
}
// Starting from the leftmost character
for (i = 0; i < n; i++)
{
Boolean flag = false;
// For every character smaller than str[i]
for (j = 0; j < str[i] - 'a'; j++)
{
// If there is a character in str which is
// smaller than str[i] and appears after it
if (chk[j] > chk[str[i] - 'a'])
{
flag = true;
break;
}
}
// If the required character pair is found
if (flag)
break;
}
// If swapping is possible
if (i < n-1)
{
// Characters to be swapped
char ch1 = str[i];
char ch2 = (char) (j + 'a');
// For every character
for (i = 0; i < n; i++)
{
// Replace every ch1 with ch2
// and every ch2 with ch1
if (str[i] == ch1)
str[i] = ch2;
else if (str[i] == ch2)
str[i] = ch1;
}
}
return String.Join("", str);
}
// Driver code
public static void Main(String[] args)
{
String str = "ccad";
int n = str.Length;
Console.WriteLine(smallestStr(
str.ToCharArray(), n));
}
}
Javascript
<script>
// JavaScript Implementation of the above approach
var MAX = 26;
// utility function to replace a char at particular string position
String.prototype.replaceAt = function(index, replacement) {
return this.substring(0, index) + replacement + this.substring(index + replacement.length);
}
function smallestStr(str, n)
{
let i, j;
// To store the first index of
// every character of str
const chk=[];
for (i = 0; i < MAX; i++)
chk[i] = -1;
// Store the first occurring
// index every character
for (i = 0; i < n; i++) {
// If current character is appearing
// for the first time in str
if (chk[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] == -1)
chk[str[i].charCodeAt(0) - 'a'.charCodeAt(0)] = i;
}
// Starting from the leftmost character
for (i = 0; i < n; i++) {
let flag = false;
// For every character smaller than str[i]
for (j = 0; j < str[i].charCodeAt(0) - 'a'.charCodeAt(0); j++) {
// If there is a character in str which is
// smaller than str[i] and appears after it
if (chk[j] > chk[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]) {
flag = true;
break;
}
}
// If the required character pair is found
if (flag)
break;
}
// If swapping is possible
if (i < n-1) {
// Characters to be swapped
let ch1 = str[i];
let ch2 = String.fromCharCode(j + 'a'.charCodeAt(0));
// For every character
for (i = 0; i < n; i++) {
// Replace every ch1 with ch2
// and every ch2 with ch1
if (str[i] == ch1)
str=str.replaceAt(i,ch2);
else if (str[i] == ch2)
str=str.replaceAt(i,ch1);
}
}
return str;
}
// Driver Code
let str = "ccad";
let n = str.length;
document.write(smallestStr(str, n));
// This code is contributed by Ishan Khandelwal
</script>
Producción
aacd