Counts the number of new string pairs obtained by swapping the first characters of string pairs in the given array

In this problem, we need to select a pair of strings and swap their first characters. After that, we need to calculate the total number of new pairs. We can solve this problem by swapping the first character of each pair and checking if it exists in the array.

An efficient way to solve this problem is to use a hash map data structure.

Problem Statement - We have an array containing N strings. We can select any two strings from all array elements and swap the first characters of these two strings. We need to count the total number of new string pairs generated that are not present in the array.

ExampleExample

Input – array[] = {"should", "would", "can"};

Output – 3

Explanation – The newly generated pair can be could and wan. Another pair could be who and should. The third pair could be san and chould.

Input – array[] = {"demo", "test"};

Output – 1

Explanation – The newly generated pair that does not exist in the array is temo and dest.

method 1

In this method, we will use two nested loops to get all pairs of array elements. After that we will swap the first characters of the two pairs. Next, we'll use a third nested loop to check if the array contains the pair.

algorithm

• Define the "cnt" variable and initialize it to 0 to store the total number of pairs.

• Use two nested loops to iterate through the string array and get each pair of array elements.

• Get the current pair of two strings.

• If the first characters of the two strings are not equal, swap them

• Define the "isFirst" and "isSecond" variables and initialize them with false to track whether the newly generated string is present in the array.

• Use the third nested loop to check if there is a newly generated string in the array. Additionally, the values ​​of the isFirst and isSecond variables are updated based on the strings in the array.

• If there is neither the first string nor the second string in the array, increase the value of 'cnt' by 1.

• Return the value of the 'cnt' variable.

Example

#include <iostream>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
   // Stores the count of pairs
   int cnt = 0;
   // Get all the pairs of strings
   for (int i = 0; i < len; i++){
      for (int j = i + 1; j < len; j++){
         // store single pair of strings
         string first = array[i], second = array[j];
         // If both strings' first characters are not equal, swap them.
         if (first[0] != second[0]){
            swap(first[0], second[0]);
            bool isFirst = false;
            bool isSecond = false;
            // Check whether the strings are present in the array or not
            for (int k = 0; k < len; k++){
               if (array[k] == first){
                  isFirst = true;
               }
                  if (array[k] == second){
                     isSecond = true;
                  }
              }
               // If both the strings are present in the array, then increment the cnt by 1
                if (isFirst == false && isSecond == false){
                    cnt++;
              }
          }
       }
    }
    return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

Output

Total number of new pairs we can generate by swapping the first characters of given strings is 3

Time complexity - O(N^3), because we use three nested loops.

Space complexity – O(1)

Method Two

In this method, we will use the map data structure to store all the array values ​​in the map. Afterwards, we can check if the map contains the newly generated string. If not, we can increase the count by 1.

algorithm

• Define variable ‘cnt’

• Loop through the string array and store all array values ​​in the map.

• Use two nested loops to get all pairs of array elements.

• Get pairs of strings and store them in the "first" and "second" variables.

• If the first characters of two strings are not equal, swap them.

• In the map, check whether the newly generated string is included. If not, increase the value of "cnt" by 1.

• Return the 'cnt' value.

Example

#include <iostream>
#include <unordered_map>
using namespace std;

// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
    // to store the total number of new pairs
    int cnt = 0;
    // add all strings to the array map
    unordered_map<string, int> str_map;
    for (int i = 0; i < len; i++){
       str_map[array[i]]++;
    }
    //find all pairs of strings that can be formed by swapping the first character of the strings
    for (int i = 0; i < len; i++){
       for (int j = i + 1; j < len; j++){
          // get the current pair of strings
          string first = array[i];
          string second = array[j];
          // If the first character of both strings is not the same, then swap them
          if (first[0] != second[0]){
             swap(first[0], second[0]);
             // If both strings are not present in the map, then the increment count
             if (str_map[first] == 0 && str_map[second] == 0){
                cnt++;
               }
            }
         }
      }
   return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

Output

Total number of new pairs we can generate by swapping the first characters of given strings is 3

Time complexity - O(N^2), because we use two nested loops.

Space complexity – O(N) because we use mapping to store all array elements.

We learn the total number of newly generated pairs by swapping the first characters of any array elements. We optimized the code for the second method in terms of time complexity, but the first code is better in terms of space complexity.

The above is the detailed content of Counts the number of new string pairs obtained by swapping the first characters of string pairs in the given array. For more information, please follow other related articles on the PHP Chinese website!