Dada una string str que consta de alfabetos ingleses en minúsculas, la tarea es convertir la string para que contenga solo caracteres distintos. Cualquier carácter de la string puede ser reemplazado por cualquier otro carácter en minúsculas (el número de reemplazos debe ser mínimo). Imprime la string modificada.
Ejemplos:
Entrada: str = “geeksforgeeks”
Salida: abcdhforgieks
Entrada: str = “bbcaacgkkk”
Salida: dbefacghik
Enfoque: si la longitud de la string es > 26 , entonces no será posible que la string tenga todos los caracteres distintos.
De lo contrario, cuente la aparición de cada uno de los caracteres de la string y, para los caracteres que aparecen más de una vez, reemplácelos con algún carácter que aún no haya aparecido en la string. Imprime la string modificada al final.
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 return the index of the character
// that has 0 occurrence starting from index i
int nextZero(int i, int occurrences[])
{
while (i < 26)
{
// If current character has 0 occurrence
if (occurrences[i] == 0)
return i;
i++;
}
// If no character has 0 occurrence
return -1;
}
// Function to return the modified string
// which consists of distinct characters
string getModifiedString(string str)
{
int n = str.length();
// String cannot consist of
// all distinct characters
if (n > 26)
return "-1";
string ch = str;
int i, occurrences[26] = {0};
// Count the occurrences for
// each of the character
for (i = 0; i < n; i++)
occurrences[ch[i] - 'a']++;
// Index for the first character
// that hasn't appeared in the string
int index = nextZero(0, occurrences);
for (i = 0; i < n; i++)
{
// If current character appeared more
// than once then it has to be replaced
// with some character that
// hasn't occurred yet
if (occurrences[ch[i] - 'a'] > 1)
{
// Decrement current character's occurrence by 1
occurrences[ch[i] - 'a']--;
// Replace the character
ch[i] = (char)('a' + index);
// Update the new character's occurrence
// This step can also be skipped as
// we'll never encounter this character
// in the string because it has
// been added just now
occurrences[index] = 1;
// Find the next character that hasn't occurred yet
index = nextZero(index + 1, occurrences);
}
}
cout << ch << endl;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
getModifiedString(str);
}
// This code is contributed by Arnab Kundu
Java
// Java implementation of the approach
class GFG {
// Function to return the index of the character
// that has 0 occurrence starting from index i
static int nextZero(int i, int occurrences[])
{
while (i < occurrences.length) {
// If current character has 0 occurrence
if (occurrences[i] == 0)
return i;
i++;
}
// If no character has 0 occurrence
return -1;
}
// Function to return the modified string
// which consists of distinct characters
static String getModifiedString(String str)
{
int n = str.length();
// String cannot consist of all distinct characters
if (n > 26)
return "-1";
char ch[] = str.toCharArray();
int i, occurrences[] = new int[26];
// Count the occurrences for each of the character
for (i = 0; i < n; i++)
occurrences[ch[i] - 'a']++;
// Index for the first character
// that hasn't appeared in the string
int index = nextZero(0, occurrences);
for (i = 0; i < n; i++) {
// If current character appeared more than once then
// it has to be replaced with some character
// that hasn't occurred yet
if (occurrences[ch[i] - 'a'] > 1) {
// Decrement current character's occurrence by 1
occurrences[ch[i] - 'a']--;
// Replace the character
ch[i] = (char)('a' + index);
// Update the new character's occurrence
// This step can also be skipped as we'll never encounter
// this character in the string because
// it has been added just now
occurrences[index] = 1;
// Find the next character that hasn't occurred yet
index = nextZero(index + 1, occurrences);
}
}
// Return the modified string
return String.valueOf(ch);
}
// Driver code
public static void main(String arr[])
{
String str = "geeksforgeeks";
System.out.print(getModifiedString(str));
}
}
Python3
# Python3 implementation of the approach
# Function to return the index of the character
# that has 0 occurrence starting from index i
def nextZero(i, occurrences):
while i < 26:
# If current character has 0 occurrence
if occurrences[i] == 0:
return i
i += 1
# If no character has 0 occurrence
return -1
# Function to return the modified string
# which consists of distinct characters
def getModifiedString(str):
n = len(str)
# String cannot consist of
# all distinct characters
if n > 26:
return "-1"
ch = str
ch = list(ch)
occurrences = [0] * 26
# Count the occurrences for
# each of the character
for i in range(n):
occurrences[ord(ch[i]) - ord('a')] += 1
# Index for the first character
# that hasn't appeared in the string
index = nextZero(0, occurrences)
for i in range(n):
# If current character appeared more
# than once then it has to be replaced
# with some character that
# hasn't occurred yet
if occurrences[ord(ch[i]) - ord('a')] > 1:
# Decrement current character's occurrence by 1
occurrences[ord(ch[i]) - ord('a')] -= 1
# Replace the character
ch[i] = chr(ord('a') + index)
# Update the new character's occurrence
# This step can also be skipped as
# we'll never encounter this character
# in the string because it has
# been added just now
occurrences[index] = 1
# Find the next character
# that hasn't occurred yet
index = nextZero(index + 1, occurrences)
ch = ''.join(ch)
print(ch)
# Driver code
if __name__ == "__main__":
str = "geeksforgeeks"
getModifiedString(str)
# This code is contributed by
# sanjeev2552
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the index of the character
// that has 0 occurrence starting from index i
static int nextZero(int i, int []occurrences)
{
while (i < occurrences.Length)
{
// If current character has 0 occurrence
if (occurrences[i] == 0)
return i;
i++;
}
// If no character has 0 occurrence
return -1;
}
// Function to return the modified string
// which consists of distinct characters
static string getModifiedString(string str)
{
int n = str.Length ;
// String cannot consist of all distinct characters
if (n > 26)
return "-1";
char []ch = str.ToCharArray();
int []occurrences = new int[26];
int i ;
// Count the occurrences for each of the character
for (i = 0; i < n; i++)
occurrences[ch[i] - 'a']++;
// Index for the first character
// that hasn't appeared in the string
int index = nextZero(0, occurrences);
for (i = 0; i < n; i++)
{
// If current character appeared more than
// once then it has to be replaced with some
// character that hasn't occurred yet
if (occurrences[ch[i] - 'a'] > 1)
{
// Decrement current character's occurrence by 1
occurrences[ch[i] - 'a']--;
// Replace the character
ch[i] = (char)('a' + index);
// Update the new character's occurrence
// This step can also be skipped
// as we'll never encounter
// this character in the string because
// it has been added just now
occurrences[index] = 1;
// Find the next character that hasn't occurred yet
index = nextZero(index + 1, occurrences);
}
}
string s = new string(ch) ;
// Return the modified string
return s ;
}
// Driver code
public static void Main()
{
string str = "geeksforgeeks";
Console.WriteLine(getModifiedString(str));
}
}
// This code is contributed by Ryuga
Javascript
<script>
// Javascript implementation of the approach
// Function to return the index of the character
// that has 0 occurrence starting from index i
function nextZero(i, occurrences)
{
while (i < occurrences.length)
{
// If current character has 0 occurrence
if (occurrences[i] == 0)
return i;
i++;
}
// If no character has 0 occurrence
return -1;
}
// Function to return the modified string
// which consists of distinct characters
function getModifiedString(str)
{
let n = str.length ;
// String cannot consist of all distinct characters
if (n > 26)
return "-1";
let ch = str.split('');
let occurrences = new Array(26);
occurrences.fill(0);
let i ;
// Count the occurrences for each of the character
for (i = 0; i < n; i++)
occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()]++;
// Index for the first character
// that hasn't appeared in the string
let index = nextZero(0, occurrences);
for (i = 0; i < n; i++)
{
// If current character appeared more than
// once then it has to be replaced with some
// character that hasn't occurred yet
if (occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()] > 1)
{
// Decrement current character's occurrence by 1
occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()]--;
// Replace the character
ch[i] = String.fromCharCode('a'.charCodeAt() + index);
// Update the new character's occurrence
// This step can also be skipped
// as we'll never encounter
// this character in the string because
// it has been added just now
occurrences[index] = 1;
// Find the next character that hasn't occurred yet
index = nextZero(index + 1, occurrences);
}
}
let s = ch.join("");
// Return the modified string
return s ;
}
let str = "geeksforgeeks";
document.write(getModifiedString(str));
// This code is contributed by vaibhavrabadiya117.
</script>
Producción:
abcdhforgieks
Publicación traducida automáticamente
Artículo escrito por sree_hari_sanjeev y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA