HomeSoftware DevelopmentSteadiness the prevalence of distinctive characters

Steadiness the prevalence of distinctive characters

Given two strings, word1, and word2, the place every string has a 0-based index. A transfer is outlined as choosing two indices, i and j, such that 0 ≤ i < word1.size and 0 ≤ j < word2.size, and exchanging the characters at these indices in word1 and word2. Decide whether it is potential to make precisely one transfer to make the variety of distinctive characters in each word1 and word2 equal. Return true whether it is potential, and false in any other case.


Enter: word1 = “cdefg”, word2 = “hijkl”
Output: true
Rationalization: Each ensuing strings could have 5 distinct characters, no matter which indices we swap.

Enter: word1 = “fh”, word2 = “b”
Output: false
Rationalization: Any pair of swaps would yield two distinct characters within the first string, and one within the second string.

Strategy: To unravel the issue comply with the under concept/instinct:

Since we will select any indices from each strings to swap and on the finish we simply want each to have the identical variety of distinct characters. The one factor that issues is which alphabet (‘a’, ‘b’, ‘c’, …) we select from word1 and which alphabet (‘a’, ‘b’, ‘c’, …) we select from word2 to swap. Since, solely lowercase(26 alphabets) are there. We are able to strive swapping all potential alphabet pairs between the 2.

Comply with the under steps to unravel the issue:

  •   Create two maps to retailer the frequency of characters in every phrase.
  •   Loop by every potential pair of characters, c1, and c2, from ‘a’ to ‘z’.
  •   If c1 is present in word1 and c2 is present in word2, take away c1 from word1’s map and add c2, and take away c2 from word2’s map and add c1.
  •  Verify if the sizes of the maps are equal. If they’re, it implies that each phrases now have the identical variety of distinct characters and the result’s true.
  •  If the map sizes usually are not equal, put again c1 in word1’s map and c2 in word2’s map to reset the maps.

In brief, the process entails swapping pairs of characters within the phrases, checking if the variety of distinct characters stays the identical and if not, resetting the phrases to their unique state.

Beneath is the implementation for the above method:


// Cpp code for the above method
#embody <bits/stdc++.h>
utilizing namespace std;

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

    // Made this helper fn for simple
    // insert/ elimination from map

    // Increment freq for char
    // to be inserted

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

        // If freq of that
        // char reaches zero,

    // Then take away the important thing
    // from map

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

    // Retailer freq of chars in
    // word1 in mp1
    for (char w1 : word1)

    // Retailer freq of chars in
    // word2 in mp2
    for (char w2 : word2)

    for (char c1 = 'a'; c1 <= 'z'; c1++) {
        for (char c2 = 'a'; c2 <= 'z'; c2++)  mp2.depend(c2) == 0)

                // If any of the char
                // isn't current
                // then skip

            insertAndRemove(mp1, c2, c1);

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

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

            // If measurement of each maps are
            // equal then potential
            // return true

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

            // Insert c1 again to word1
            // and take away c2 from word1
            insertAndRemove(mp2, c2, c1);

            // Insert c2 again to word2
            // and take away c1 from word2

    return false;

// Drivers code
int essential()

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

    // Perform Name
    if (balanceOccurences(word1, word2))
        cout << "True";
        cout << "False";
    return 0;

Time Complexity:   O(N+M+26*26) i.e. O(N+M): the place N is the dimensions of word1 and M is the dimensions of word2. We iterated each strings as soon as, and a hard and fast 26*26 for loop (This 26*26 is fixed, and doesn’t depend upon enter variables i.e. string sizes N or M)
Auxiliary House:  O(26) i.e O(1): Since word1 and word2 encompass solely lowercase English letters, so each map can have 26 parts solely at max


Most Popular

Recent Comments