InMy.Live

Étant donné deux chaînes, mot1et mot2, où chaque chaîne a un index de base 0. Un mouvement est défini comme la sélection de deux indices, i et j, tels que 0 ≤ i < mot1.longueur et 0 ≤ j < mot2.longueur, et en échangeant les caractères à ces indices dans mot1 et mot2. Déterminez s’il est possible de faire exactement un mouvement pour rendre le nombre de caractères uniques dans le mot1 et le mot2 égaux. Renvoie true si c’est possible, et false sinon.

Exemples:

Saisir: mot1 = “cdefg”, mot2 = “hijkl”
Sortir: vrai
Explication: Les deux chaînes résultantes auront 5 caractères distincts, quels que soient les indices que nous permutons.

Saisir: mot1 = “fh”, mot2 = “b”
Sortir: FAUX
Explication: Toute paire de swaps produirait deux caractères distincts dans la première chaîne et un dans la seconde chaîne.

Approche: Pour résoudre le problème, suivez l’idée/l’intuition ci-dessous :

Puisque nous pouvons choisir n’importe quel index des deux chaînes à échanger et à la fin, nous avons juste besoin que les deux aient le même nombre de caractères distincts. La seule chose qui importe est quel alphabet (‘a’, ‘b’, ‘c’, …) nous choisissons du mot1 et quel alphabet (‘a’, ‘b’, ‘c’, …) nous choisissons du mot2 à échanger. Depuis, seules les minuscules (26 alphabets) sont là. Nous pouvons essayer d’échanger toutes les paires d’alphabets possibles entre les deux.

Suivez les étapes ci-dessous pour résoudre le problème :

• Créez deux cartes pour stocker la fréquence des caractères dans chaque mot.
• Parcourez chaque paire de caractères possible, c1 et c2, de ‘a’ à ‘z’.
• Si c1 est trouvé dans le mot1 et c2 dans le mot2, supprimez c1 de la carte de mot1 et ajoutez c2, et supprimez c2 de la carte de mot2 et ajoutez c1.
• Vérifiez si les tailles des cartes sont égales. Si c’est le cas, cela signifie que les deux mots ont maintenant le même nombre de caractères distincts et que le résultat est vrai.
• Si les tailles de carte ne sont pas égales, remettez c1 dans la carte de mot1 et c2 dans la carte de mot2 pour réinitialiser les cartes.

En bref, la procédure consiste à échanger des paires de caractères dans les mots, à vérifier si le nombre de caractères distincts reste le même et, dans le cas contraire, à réinitialiser les mots à leur état d’origine.

Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :

// Cpp code for the above approach
#include <bits/stdc++.h>
using namespace std;

void insertAndRemove(unordered_map<char, int>& mp,
                     char toInsert, char toRemove)
{

    // Made this helper fn for easy
    // insert/ removal from map

    // Increment freq for char
    // to be inserted
    mp[toInsert]++;

    // Decrement freq for char
    // to be removed
    mp[toRemove]--;
    if (mp[toRemove] == 0)

        // If freq of that
        // char reaches zero,
        mp.erase(toRemove);

    // Then remove the key
    // from map
}

bool balanceOccurences(string word1, string word2)
{
    unordered_map<char, int> mp1, mp2;

    // Store freq of chars in
    // word1 in mp1
    for (char w1 : word1)
        mp1[w1]++;

    // Store freq of chars in
    // word2 in mp2
    for (char w2 : word2)
        mp2[w2]++;

    for (char c1 = 'a'; c1 <= 'z'; c1++) {
        for (char c2 = 'a'; c2 <= 'z'; c2++) {
            if (mp1.count(c1) == 0 || mp2.count(c2) == 0)

                // If any of the char
                // is not present
                // then skip
                continue;

            insertAndRemove(mp1, c2, c1);

            // Insert c2 to word1 and
            // remove c1 from word1
            insertAndRemove(mp2, c1, c2);
            // Insert c1 to word2 and
            // remove c2 from word2

            if (mp1.size() == mp2.size())
                return true;

            // If size of both maps are
            // equal then possible
            // return true

            // Reset back the maps
            insertAndRemove(mp1, c1, c2);

            // Insert c1 back to word1
            // and remove c2 from word1
            insertAndRemove(mp2, c2, c1);

            // Insert c2 back to word2
            // and remove c1 from word2
        }
    }

    return false;
}

// Drivers code
int main()
{

    string word1 = "cdefg";
    string word2 = "hijkl";

    // Function Call
    if (balanceOccurences(word1, word2))
        cout << "True";
    else
        cout << "False";
    return 0;
}

Complexité temporelle : O(N+M+26*26) c’est-à-dire O(N+M) : où N est la taille du mot1 et M est la taille du mot2. Nous avons itéré les deux chaînes une fois et une boucle for fixe 26*26 (ce 26*26 est constant et ne dépend pas des variables d’entrée, c’est-à-dire des tailles de chaîne N ou M)
Espace Auxiliaire : O(26) c’est-à-dire O(1): Étant donné que word1 et word2 ne sont constitués que de lettres anglaises minuscules, les deux cartes ne peuvent avoir que 26 éléments au maximum