Dada una array arr[] que consiste en N strings, la tarea es modificar la array reemplazando las strings duplicadas agregando un número y tal que todas las strings en la array sean únicas.
Ejemplos:
Entrada: S = {“aa”, “bb”, “cc”, “bb”, “aa”, “aa”, “aa”}
Salida: {“aa”, “bb”, “cc”, “bb1 ”, “aa1”, “aa2”, “aa3”}
Explicación:
La salida de la segunda aparición de “bb” es “bb1”
La salida de la segunda aparición de “aa” es “aa1”
La salida de la tercera aparición de “aa” es “aa2”
La salida de la cuarta ocurrencia de “aa” es “aa3”Entrada: S = {“aa”, “bb”, “cc”, “aa”}
Salida: {“aa”, “bb”, “cc”, “aa1”}
Enfoque: la idea es atravesar la array y almacenar la frecuencia de cada string en arr[] en un Hashmap . Mientras almacena la frecuencia, si la string no tiene ocurrencias anteriores, deje la string sin cambios. De lo contrario, agregue su frecuencia al final. Finalmente, imprima todas las strings únicas presentes en la array arr[] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to replace duplicate strings // by alphanumeric strings to make all // strings in the array unique void replaceDuplicates( vector<string>& names) { // Store the frequency of strings unordered_map<string, int> hash; // Iterate over the array for (int i = 0; i < names.size(); i++) { // For the first occurrence, // update the frequency count if (hash.count(names[i]) == 0) hash[names[i]]++; // Otherwise else { int count = hash[names[i]]++; // Append frequency count // to end of the string names[i] += to_string(count); } } // Print the modified array for (int i = 0; i < names.size(); i++) { cout << names[i] << " "; } } // Driver Code int main() { vector<string> str = { "aa", "bb", "cc", "bb", "aa", "aa", "aa" }; // Function Call replaceDuplicates(str); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to replace duplicate strings // by alphanumeric strings to make all // strings in the array unique static void replaceDuplicates(String[] names) { // Store the frequency of strings HashMap<String, Integer> hash = new HashMap<>(); // Iterate over the array for(int i = 0; i < names.length; i++) { // For the first occurrence, // update the frequency count if (!hash.containsKey(names[i])) hash.put(names[i], 1); // Otherwise else { int count = hash.get(names[i]); hash.put(names[i], hash.get(names[i]) + 1); // Append frequency count // to end of the string names[i] += Integer.toString(count); } } // Print the modified array for(int i = 0; i < names.length; i++) { System.out.print(names[i] + ' '); } } // Driver Code public static void main(String[] args) { String[] str = { "aa", "bb", "cc", "bb", "aa", "aa", "aa" }; // Function Call replaceDuplicates(str); } } // This code is contributed by akhilsaini
Python3
# Python3 program for the above approach # Function to replace duplicate strings # by alphanumeric strings to make all # strings in the array unique def replaceDuplicates(names): # Store the frequency of strings hash = {} # Iterate over the array for i in range(0, len(names)): # For the first occurrence, # update the frequency count if names[i] not in hash: hash[names[i]] = 1 # Otherwise else: count = hash[names[i]] hash[names[i]] += 1 # Append frequency count # to end of the string names[i] += str(count) # Print the modified array for i in range(0, len(names)): print(names[i], end = ' ') # Driver Code if __name__ == '__main__': str1 = [ "aa", "bb", "cc", "bb", "aa", "aa", "aa" ] # Function Call replaceDuplicates(str1) # This code is contributed by akhilsaini
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to replace duplicate strings // by alphanumeric strings to make all // strings in the array unique static void replaceDuplicates(string[] names) { // Store the frequency of strings Dictionary<string, int> hash = new Dictionary<string, int>(); // Iterate over the array for(int i = 0; i < names.Length; i++) { // For the first occurrence, // update the frequency count if (!hash.ContainsKey(names[i])) hash[names[i]] = 1; // Otherwise else { int count = hash[names[i]]; hash[names[i]] += 1; // Append frequency count // to end of the string names[i] += count.ToString(); } } // Print the modified array for(int i = 0; i < names.Length; i++) { Console.Write(names[i] + ' '); } } // Driver Code public static void Main() { string[] str = { "aa", "bb", "cc", "bb", "aa", "aa", "aa" }; // Function Call replaceDuplicates(str); } } // This code is contributed by akhilsaini
Javascript
<script> // Javascript program for the above approach // Function to replace duplicate strings // by alphanumeric strings to make all // strings in the array unique function replaceDuplicates( names) { // Store the frequency of strings var hash = new Map(); // Iterate over the array for (var i = 0; i < names.length; i++) { // For the first occurrence, // update the frequency count if (!hash.has(names[i])) hash.set(names[i],1); // Otherwise else { var count = hash.get(names[i]); hash.set(names[i],hash.get(names[i])+1); // Append frequency count // to end of the string names[i] += count.toString(); } } // Print the modified array for (var i = 0; i < names.length; i++) { document.write( names[i] + " "); } } // Driver Code var str = [ "aa", "bb", "cc", "bb", "aa", "aa", "aa" ]; // Function Call replaceDuplicates(str); </script>
aa bb cc bb1 aa1 aa2 aa3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)