Verifique si las strings dadas se pueden hacer iguales intercambiando dos caracteres de strings iguales o diferentes

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)

Publicación traducida automáticamente

Artículo escrito por nk14646 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *