Compruebe si las strings se pueden igualar intercambiando caracteres

Dada una array de N strings, la tarea es encontrar si es posible igualar todas las strings realizando las siguientes operaciones:

• Elimine un carácter de la i ^-ésima string e insértelo en una posición arbitraria en la j ^-ésima string. ( i y j pueden ser lo mismo)
• Puede realizar esta operación cualquier número de veces.

Ejemplos:

Entrada: N = 2, S[] = {“caa”, “cbb”}
Salida: YES 
Explicación: Es posible intercambiar la ‘a’ de la primera string con ‘b’ en la segunda string para que ambas strings sean iguales.
Las strings se pueden hacer «cab» y «cab» o «cba» y «cba».

Entrada: N = 3, S[] = {“cba”, “cba”, “cbb”} 
Salida: NO
Explicación: Es imposible hacer que todas las strings sean iguales.

Planteamiento: La idea para resolver el problema es la siguiente:

Debido a las operaciones, cualquier string se puede organizar de cualquier forma. Entonces, para hacer que las strings sean iguales, todas las strings deben tener todos los caracteres el mismo número de veces. 
Entonces pueden hacerse iguales si la frecuencia de cada carácter en todas las strings debe ser un múltiplo de N .

Siga los pasos mencionados a continuación para implementar el problema:

• Recorra la array de strings y para cada string haga lo siguiente:
  • Atraviesa esa cuerda.
  • Cuente la frecuencia de cada carácter.
• Si las frecuencias de todos los caracteres de todas las strings son múltiplos de N, entonces solo se pueden hacer iguales.
• De lo contrario, vuelve que es imposible.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if all the strings can be made equal
bool sameString(int N, string s[])
{
    // Vector of 26 to store the frequency
    // of each alphabet(characters).
    vector<int> cnt(26);
 
    for (int i = 0; i < N; ++i) {
        for (char ch : s[i]) {
 
            // Incrementing the frequency of
            // alphabet (subtracting and
            // finding the index, then
            // incrementing index by one.)
            ++cnt[ch - 'a'];
        }
    }
 
    bool ans = true;
    for (int i = 0; i < 26; ++i) {
 
        // Checking if divisible by N or not
        if (cnt[i] % N != 0) {
 
            // If not divisible at any time,
            // then its not possible to
            // divide equally.
            ans = false;
            break;
        }
    }
 
    // Return the final result to print
    // yes or no.
    return ans;
}
 
// Drivers code
int main()
{
 
    // Number of strings in the given input.
    int N = 3;
    string S[] = { "cba", "cba", "cbb" };
    bool ans;
 
    // Function call
    ans = sameString(N, S);
    cout << (ans ? "YES" : "NO");
    return 0;
}

// Java code to implement the approach:
import java.util.*;
 
class GFG{
 
// Function to check if all the Strings can be made equal
static boolean sameString(int N, String s[])
{
    // Vector of 26 to store the frequency
    // of each alphabet(characters).
    int[] cnt = new int[26];
 
    for (int i = 0; i < N; ++i) {
        String st = s[i];
        for (int j = 0;j<st.length();j++) {
 
            // Incrementing the frequency of
            // alphabet (subtracting and
            // finding the index, then
            // incrementing index by one.)
            ++cnt[st.charAt(j) - 'a'];
        }
    }
 
    boolean ans = true;
    for (int i = 0; i < 26; ++i) {
 
        // Checking if divisible by N or not
        if (cnt[i] % N != 0) {
 
            // If not divisible at any time,
            // then its not possible to
            // divide equally.
            ans = false;
            break;
        }
    }
 
    // Return the final result to print
    // yes or no.
    return ans;
}
 
// Drivers code
public static void main(String[] args)
{
 
    // Number of Strings in the given input.
    int N = 3;
    String S[] = { "cba", "cba", "cbb" };
    boolean ans;
 
    // Function call
    ans = sameString(N, S);
    System.out.print((ans ? "YES" : "NO"));
}
}
 
// This code is contributed by shikhasingrajput

# Python3 code to implement the approach:
 
# Function to check if all the strings can be made equal
def sameString(N, s) :
 
    # Vector of 26 to store the frequency
    # of each alphabet(characters).
    cnt = [0]*26;
 
    for i in range(N):
        for ch in s[i] :
 
            # Incrementing the frequency of
            # alphabet (subtracting and
            # finding the index, then
            # incrementing index by one.)
            cnt[ord(ch) - ord('a')]  += 1;
 
 
    ans = True;
    for i in range(26) :
 
        # Checking if divisible by N or not
        if (cnt[i] % N != 0) :
 
            # If not divisible at any time,
            # then its not possible to
            # divide equally.
            ans = False;
            break;
 
    # Return the final result to print
    # yes or no.
    return ans;
 
# Drivers code
if __name__ == "__main__" :
 
    # Number of strings in the given input.
    N = 3;
    S = [ "cba", "cba", "cbb" ];
     
    # Function call
    ans = sameString(N, S);
    if ans:
        print("YES")
    else:
        print("NO")
         
    # This Code is contributed by AnkThon

// C# code to implement the above approach
using System;
 
public class GFG {
 
  // Function to check if all the Strings can be made
  // equal
  static bool sameString(int N, string[] s)
  {
    // Vector of 26 to store the frequency
    // of each alphabet(characters).
    int[] cnt = new int[26];
 
    for (int i = 0; i < N; i++) {
      String st = s[i];
      for (int j = 0; j < st.Length; j++) {
        // Incrementing the frequency of
        // alphabet (subtracting and
        // finding the index, then
        // incrementing index by one.)
        ++cnt[st[j] - 'a'];
      }
    }
    bool ans = true;
    for (int i = 0; i < 26; i++) {
      // Checking if divisible by N or not
      if (cnt[i] % N != 0) {
        // If not divisible at any time,
        // then its not possible to
        // divide equally.
        ans = false;
        break;
      }
    }
    // Return the final result to print
    // yes or no.
    return ans;
  }
 
  static public void Main()
  {
    // Code
 
    // Number of Strings in the given input.
    int N = 3;
    string[] S = new string[3] { "cba", "cba", "cbb" };
    bool ans;
 
    // Function call
    ans = sameString(N, S);
    Console.WriteLine((ans ? "YES" : "NO"));
  }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
    // JavaScript code to implement the approach:
 
 
    // Function to check if all the strings can be made equal
    const sameString = (N, s) => {
        // Vector of 26 to store the frequency
        // of each alphabet(characters).
        let cnt = new Array(26).fill(0);
 
        for (let i = 0; i < N; ++i) {
            for (let ch in s[i]) {
 
                // Incrementing the frequency of
                // alphabet (subtracting and
                // finding the index, then
                // incrementing index by one.)
                ++cnt[s[i].charCodeAt(ch) - 'a'.charCodeAt(0)];
            }
        }
 
        let ans = true;
        for (let i = 0; i < 26; ++i) {
 
            // Checking if divisible by N or not
            if (cnt[i] % N != 0) {
 
                // If not divisible at any time,
                // then its not possible to
                // divide equally.
                ans = false;
                break;
            }
        }
 
        // Return the final result to print
        // yes or no.
        return ans;
    }
 
    // Drivers code
 
    // Number of strings in the given input.
    let N = 3;
    let S = ["cba", "cba", "cbb"];
    let ans;
 
    // Function call
    ans = sameString(N, S);
    if (ans) document.write("YES");
    else document.write("NO");
 
    // This code is contributed by rakeshsahni
 
</script>

NO

Complejidad de Tiempo: O(N * M) Donde M es la longitud máxima de una string
Espacio Auxiliar: O(1).