Dada una array arr[] que consta de N strings, la tarea es ordenar la array en orden ascendente después de modificar cada string eliminando todos los caracteres que no sean potencia perfecta de 2 y luego ordenar la string modificada en orden decreciente.
Ejemplos:
Entrada: arr[] = {“aaacbb”, “geeks”, “aaa”}
Salida: cbb skgee
Explicación: Las
siguientes son las strings modificadas en la array arr[]:
- Para la string “aaacbb”: La frecuencia de a no es la potencia de 2. Por lo tanto, eliminar ‘a’ modifica la string a “cbb”. Ahora, ordenar la string «cbb» en orden creciente de frecuencia modifica la string a «cbb».
- Para la string «geeks»: la frecuencia de cada carácter es una potencia de 2. Ahora, ordenar la string «geeks» en orden creciente de frecuencia modifica la string a «skgee».
- Para la string “aaa”: La frecuencia de a no es la potencia de 2. Por lo tanto, eliminar ‘a’ modifica la string a “”.
Por lo tanto, ordenar las strings anteriores en orden creciente da {“cbb”, “skgee”}.
Entrada: S[] = {“c”, “a”, “b”}
Salida: abc
Enfoque: el problema dado se puede resolver usando Hashing para almacenar las frecuencias de todos los caracteres para cada string y luego realizar las operaciones dadas. Siga los pasos a continuación para resolver el problema:
- Recorra la array dada de strings arr[] y para cada string realice las siguientes operaciones:
- Almacena la frecuencia de cada carácter en un Mapa .
- Cree una string vacía, digamos T , para almacenar la string modificada.
- Ahora recorra el mapa y agregue los caracteres cuya frecuencia está en la potencia de 2 a la string T .
- Ordene la string T en orden creciente y agréguela a una array de strings res[] .
- Ordene la array res[] en orden creciente .
- Después de completar los pasos anteriores, imprima las strings en la array res[] como resultado.
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 check if N is power of
// 2 or not
bool isPowerOfTwo(int n)
{
// Base Case
if (n == 0)
return false;
// Return true if N is power of 2
return (ceil(log2(n))
== floor(log2(n)));
}
// Function to print array of strings
// in ascending order
void printArray(vector<string> res)
{
// Sort strings in ascending order
sort(res.begin(), res.end());
// Print the array
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
}
// Function to sort the strings after
// modifying each string according to
// the given conditions
void sortedStrings(string S[], int N)
{
// Store the frequency of each
// characters of the string
unordered_map<char, int> freq;
// Stores the required
// array of strings
vector<string> res;
// Traverse the array of strings
for (int i = 0; i < N; i++) {
// Temporary string
string st = "";
// Stores frequency of each
// alphabet of the string
for (int j = 0;
j < S[i].size(); j++) {
// Update frequency of S[i][j]
freq[S[i][j]]++;
}
// Traverse the map freq
for (auto i : freq) {
// Check if the frequency
// of i.first is a power of 2
if (isPowerOfTwo(i.second)) {
// Update string st
for (int j = 0;
j < i.second; j++) {
st += i.first;
}
}
}
// Clear the map
freq.clear();
// Null string
if (st.size() == 0)
continue;
// Sort the string in
// descending order
sort(st.begin(), st.end(),
greater<char>());
// Update res
res.push_back(st);
}
// Print the array of strings
printArray(res);
}
// Driver Code
int main()
{
string arr[] = { "aaacbb", "geeks", "aaa" };
int N = sizeof(arr) / sizeof(arr[0]);
sortedStrings(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if N is power of
// 2 or not
static boolean isPowerOfTwo(int n)
{
// Base Case
if (n == 0)
return false;
// Return true if N is power of 2
return (Math.ceil(Math.log(n) / Math.log(2)) ==
Math.floor(Math.log(n) / Math.log(2)));
}
// Function to print array of strings
// in ascending order
static void printArray(ArrayList<String> res)
{
// Sort strings in ascending order
Collections.sort(res);
// Print the array
for(int i = 0; i < res.size(); i++)
{
System.out.print(res.get(i) + " ");
}
}
// Function to sort the strings after
// modifying each string according to
// the given conditions
static void sortedStrings(String S[], int N)
{
// Store the frequency of each
// characters of the string
HashMap<Character, Integer> freq = new HashMap<>();
// Stores the required
// array of strings
ArrayList<String> res = new ArrayList<>();
// Traverse the array of strings
for(int i = 0; i < N; i++)
{
// Temporary string
String st = "";
// Stores frequency of each
// alphabet of the string
for(int j = 0; j < S[i].length(); j++)
{
// Update frequency of S[i][j]
freq.put(S[i].charAt(j),
freq.getOrDefault(S[i].charAt(j), 0) + 1);
}
// Traverse the map freq
for(char ch : freq.keySet())
{
// Check if the frequency
// of i.first is a power of 2
if (isPowerOfTwo(freq.get(ch)))
{
// Update string st
for(int j = 0; j < freq.get(ch); j++)
{
st += ch;
}
}
}
// Clear the map
freq.clear();
// Null string
if (st.length() == 0)
continue;
// Sort the string in
// descending order
char myCharArr[] = st.toCharArray();
Arrays.sort(myCharArr);
String ns = "";
for(int j = myCharArr.length - 1; j >= 0; --j)
ns += myCharArr[j];
// Update res
res.add(ns);
}
// Print the array of strings
printArray(res);
}
// Driver Code
public static void main(String[] args)
{
String arr[] = { "aaacbb", "geeks", "aaa" };
int N = arr.length;
sortedStrings(arr, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach from collections import defaultdict import math # Function to check if N is power of # 2 or not def isPowerOfTwo(n): # Base Case if (n == 0): return False # Return true if N is power of 2 return (math.ceil(math.log2(n)) == math.floor(math.log2(n))) # Function to print array of strings # in ascending order def printArray(res): # Sort strings in ascending order res.sort() # Print the array for i in range(len(res)): print(res[i], end = " ") # Function to sort the strings after # modifying each string according to # the given conditions def sortedStrings(S, N): # Store the frequency of each # characters of the string freq = defaultdict(int) # Stores the required # array of strings res = [] # Traverse the array of strings for i in range(N): # Temporary string st = "" # Stores frequency of each # alphabet of the string for j in range(len(S[i])): # Update frequency of S[i][j] freq[S[i][j]] += 1 # Traverse the map freq for i in freq: # Check if the frequency # of i.first is a power of 2 if (isPowerOfTwo(freq[i])): # Update string st for j in range(freq[i]): st += i # Clear the map freq.clear() # Null string if (len(st) == 0): continue # Sort the string in # descending order st = list(st) st.sort(reverse=True) st = ''.join(st) # Update res res.append(st) # Print the array of strings printArray(res) # Driver Code if __name__ == "__main__": arr = [ "aaacbb", "geeks", "aaa" ] N = len(arr) sortedStrings(arr, N) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check if N is power of
// 2 or not
static bool isPowerOfTwo(int n)
{
// Base Case
if (n == 0)
return false;
// Return true if N is power of 2
return (Math.Ceiling(Math.Log(n) / Math.Log(2)) ==
Math.Floor(Math.Log(n) / Math.Log(2)));
}
// Function to print array of strings
// in ascending order
static void printArray(List<string> res)
{
// Sort strings in ascending order
(res).Sort();
// Print the array
for(int i = 0; i < res.Count; i++)
{
Console.Write(res[i] + " ");
}
}
// Function to sort the strings after
// modifying each string according to
// the given conditions
static void sortedStrings(string[] S, int N)
{
// Store the frequency of each
// characters of the string
Dictionary<char,int> freq = new Dictionary<char,int>();
// Stores the required
// array of strings
List<string> res = new List<string>();
// Traverse the array of strings
for(int i = 0; i < N; i++)
{
// Temporary string
string st = "";
// Stores frequency of each
// alphabet of the string
for(int j = 0; j < S[i].Length; j++)
{
// Update frequency of S[i][j]
if(!freq.ContainsKey(S[i][j]))
freq.Add(S[i][j],0);
freq[S[i][j]]++;
}
// Traverse the map freq
foreach(KeyValuePair<char, int> ch in freq)
{
// Check if the frequency
// of i.first is a power of 2
if (isPowerOfTwo(freq[ch.Key]))
{
// Update string st
for(int j = 0; j < freq[ch.Key]; j++)
{
st += ch.Key;
}
}
}
// Clear the map
freq.Clear();
// Null string
if (st.Length == 0)
continue;
// Sort the string in
// descending order
char[] myCharArr = st.ToCharArray();
Array.Sort(myCharArr);
string ns = "";
for(int j = myCharArr.Length - 1; j >= 0; --j)
ns += myCharArr[j];
// Update res
res.Add(ns);
}
// Print the array of strings
printArray(res);
}
// Driver Code
static public void Main ()
{
string[] arr = { "aaacbb", "geeks", "aaa" };
int N = arr.Length;
sortedStrings(arr, N);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Function to check if N is power of
// 2 or not
function isPowerOfTwo(n)
{
// Base Case
if (n == 0)
return false;
// Return true if N is power of 2
return (Math.ceil(Math.log(n) / Math.log(2)) ==
Math.floor(Math.log(n) / Math.log(2)));
}
// Function to print array of strings
// in ascending order
function printArray(res)
{
// Sort strings in ascending order
res.sort((a, b) => a - b);
// Print the array
for(let i = 0; i < res.length; i++)
{
document.write(res[i] + " ");
}
}
// Function to sort the strings after
// modifying each string according to
// the given conditions
function sortedStrings(s, N)
{
// Store the frequency of each
// characters of the string
let freq = new Map();
// Stores the required
// array of strings
let res = new Array();
// Traverse the array of strings
for(let i = 0; i < N; i++)
{
// Temporary string
let st = "";
// Stores frequency of each
// alphabet of the string
for(let j = 0; j < s[i].length; j++)
{
// Update frequency of S[i][j]
if (freq.has(s[i][j]))
{
freq.set(s[i][j], freq.get(s[i][j]) + 1)
}
else
{
freq.set(s[i][j], 1)
}
}
// Traverse the map freq
for(let ch of freq.keys())
{
// Check if the frequency
// of i.first is a power of 2
if (isPowerOfTwo(freq.get(ch)))
{
// Update string st
for(let j = 0; j < freq.get(ch); j++)
{
st += ch;
}
}
}
// Clear the map
freq.clear();
// Null string
if (st.length == 0)
continue;
// Sort the string in
// descending order
let myCharArr = st.split("");
myCharArr.sort();
let ns = "";
for(let j = myCharArr.length - 1;
j >= 0; --j)
ns += myCharArr[j];
// Update res
res.push(ns);
}
// Print the array of strings
printArray(res);
}
// Driver Code
let arr = [ "aaacbb", "geeks", "aaa" ];
let N = arr.length;
sortedStrings(arr, N);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
cbb skgee
Complejidad de tiempo: O(N * log N + M * log M), donde M es la longitud máxima de una string en S[]
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA