Dada una array de strings de igual longitud , arr[] de tamaño N , la tarea es verificar si todas las strings pueden igualarse intercambiando repetidamente cualquier par de caracteres de strings iguales o diferentes de la array dada. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” .
Ejemplos:
Entrada: arr[] = { “acbdd”, “abcee” }
Salida: SÍ
Explicación:
Intercambiar arr[0][1] y arr[0][2] modifica arr[] a { “abcdd”, “abcee” }
Intercambiar arr[0][3] y arr[1][4] modifica arr[] a { “abced”, “abced” }
Por lo tanto, la salida requerida es “SÍ” .Entrada : arr[] = { “abb”, “acc”, “abc” }
Salida: SÍ
Explicación:
Intercambiar arr[0][2] con arr[1][1] modifica arr[] a { “abc”, “abc”, “abc” }.
Por lo tanto, la salida requerida es «SÍ» .
Enfoque: La idea es contar la frecuencia de cada carácter distinto de todas las strings y comprobar si la frecuencia de cada carácter distinto es divisible por N o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos cntFreq[] , para almacenar la frecuencia de cada carácter distinto de todas las strings.
- Recorra la array y para cada string encontrada, cuente la frecuencia de cada carácter distinto de la string.
- Recorra la array cntFreq[] usando la variable i . Para cada i -ésimo carácter, compruebe si cntFreq[i] es divisible por N o no. Si se encuentra que es falso, escriba «NO» .
- De lo contrario, escriba “SI” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if all strings can be
// made equal by swapping any pair of
// characters from the same or different strings
bool isEqualStrings(string arr[], int N)
{
// Stores length of string
int M = arr[0].length();
// Store frequency of each distinct
// character of the strings
int cntFreq[256] = { 0 };
// Traverse the array
for (int i = 0; i < N; i++) {
// Iterate over the characters
for (int j = 0; j < M; j++) {
// Update frequency
// of arr[i][j]
cntFreq[arr[i][j] - 'a']++;
}
}
// Traverse the array cntFreq[]
for (int i = 0; i < 256; i++) {
// If cntFreq[i] is
// divisible by N or not
if (cntFreq[i] % N != 0) {
return false;
}
}
return true;
}
// Driver Code
int main()
{
string arr[] = { "aab", "bbc", "cca" };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
if (isEqualStrings(arr, N)) {
cout << "YES";
}
else {
cout << "NO";
}
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to check if all strings can be
// made equal by swapping any pair of
// characters from the same or different strings
static boolean isEqualStrings(String[] arr, int N)
{
// Stores length of string
int M = arr[0].length();
// Store frequency of each distinct
// character of the strings
int[] cntFreq = new int[256];
for(int i = 0; i < N; i++)
{
cntFreq[i] = 0;
}
// Traverse the array
for(int i = 0; i < N; i++)
{
// Iterate over the characters
for(int j = 0; j < M; j++)
{
// Update frequency
// of arr[i].charAt(j)
cntFreq[arr[i].charAt(j) - 'a'] += 1;
}
}
// Traverse the array cntFreq[]
for(int i = 0; i < 256; i++)
{
// If cntFreq[i] is
// divisible by N or not
if (cntFreq[i] % N != 0)
{
return false;
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
String[] arr = { "aab", "bbc", "cca" };
int N = arr.length;
// Function Call
if (isEqualStrings(arr, N))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
// This code is contributed by AnkThon
Python3
# Python3 program to implement
# the above approach
# Function to check if all strings can
# be made equal by swapping any pair of
# characters from the same or different
# strings
def isEqualStrings(arr, N):
# Stores length of string
M = len(arr[0])
# Store frequency of each distinct
# character of the strings
cntFreq = [0] * 256
# Traverse the array
for i in range(N):
# Iterate over the characters
for j in range(M):
# Update frequency
# of arr[i][j]
cntFreq[ord(arr[i][j]) - ord('a')] += 1
# Traverse the array cntFreq[]
for i in range(256):
# If cntFreq[i] is
# divisible by N or not
if (cntFreq[i] % N != 0):
return False
return True
# Driver Code
if __name__ == "__main__" :
arr = [ "aab", "bbc", "cca" ]
N = len(arr)
# Function Call
if isEqualStrings(arr, N):
print("YES")
else:
print("NO")
# This code is contributed by jana_sayantan
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check if all strings can be
// made equal by swapping any pair of
// characters from the same or different strings
static bool isEqualStrings(string[] arr, int N)
{
// Stores length of string
int M = arr[0].Length;
// Store frequency of each distinct
// character of the strings
int[] cntFreq = new int[256];
for(int i = 0; i < N; i++)
{
cntFreq[i] = 0;
}
// Traverse the array
for(int i = 0; i < N; i++)
{
// Iterate over the characters
for(int j = 0; j < M; j++)
{
// Update frequency
// of arr[i][j]
cntFreq[arr[i][j] - 'a'] += 1;
}
}
// Traverse the array cntFreq[]
for(int i = 0; i < 256; i++)
{
// If cntFreq[i] is
// divisible by N or not
if (cntFreq[i] % N != 0)
{
return false;
}
}
return true;
}
// Driver Code
public static void Main()
{
string[] arr = { "aab", "bbc", "cca" };
int N = arr.Length;
// Function Call
if (isEqualStrings(arr, N))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// javascript program of the above approach
// Function to check if all strings can be
// made equal by swapping any pair of
// characters from the same or different strings
function isEqualStrings(arr, N)
{
// Stores length of string
let M = arr[0].length;
// Store frequency of each distinct
// character of the strings
let cntFreq = new Array(256).fill(0);
for(let i = 0; i < N; i++)
{
cntFreq[i] = 0;
}
// Traverse the array
for(let i = 0; i < N; i++)
{
// Iterate over the characters
for(let j = 0; j < M; j++)
{
// Update frequency
// of arr[i].charAt(j)
cntFreq[arr[i][j] - 'a'] += 1;
}
}
// Traverse the array cntFreq[]
for(let i = 0; i < 256; i++)
{
// If cntFreq[i] is
// divisible by N or not
if (cntFreq[i] % N != 0)
{
return false;
}
}
return true;
}
// Driver Code
let arr = [ "aab", "bbc", "cca" ];
let N = arr.length;
// Function Call
if (isEqualStrings(arr, N))
{
document.write("YES");
}
else
{
document.write("NO");
}
// This code is contributed by target_2.
</script>
Producción:
YES
Complejidad de tiempo : O(N * M + 256), donde M es la longitud de la string
Espacio auxiliar: O(256)