Count the number of pairs of strings that differ in only one position

Introduction

Strings consist of alphanumeric characters, each character is associated with a determined position. Character positions range from 0 to the string length. Characters that are completely different in one position are called adjacent characters.

In this article, we will develop a code that takes as input an array of strings that are completely different in one position. Let us see the following example to understand this topic better -

Example

Example 1 - str - {"abc", "cba", "dbc", "acc"}

Output - 2

For example, in the following example, two pairs {"abc", "dbc"} and {"abc", acc"} can be generated. These strings differ in only one character position each.

In this article, we will develop a code that uses mapping to store similar strings and a pattern to get the total number of string pairs. C maps utilize key-value pairs in order to store and retrieve data with constant time complexity.

grammar

substr()

The substr() method is used to access the substring from start to end-1 in a larger string. All indexes to be accessed should be contiguous and ordered.

Parameters -

st - starting position

end - The end position at which substring access is terminated

algorithm

• Accepts a string vector, string

• Initially maintain a counter to store the count of total pairs that meet the condition.

• Maintain two maps to store identical strings and strings that satisfy patterns that preserve wildcards. Let us assume that this mapping is m1.

• Maintain another map to store similar strings. Let us assume that this mapping is m2.

• Perform iteration over the input array.

• Every time a similar type of string is observed, its corresponding count in the m2 map will be incremented

• Substrings are created by replacing individual characters of the string with wildcard characters

• Every time a similar type of pattern is observed, the corresponding count in the m1 graph is incremented

• Compute the sum of string pairs observed in m1 and m2 respectively.

• Use these summed values ​​to increment the count.

Example

The following C code snippet is used to take an array of strings as input and count the total number of pairs that differ in only one position -

//including the required libraries
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int countPairs(map<string, int> &d) {
   //maintaining the count 
   int sum = 0;
   for (auto i : d)
       sum += (i.second * (i.second - 1)) / 2;
 
   return sum;
}
//called method to calculate strings differing by one character
void chardiff(vector<string> &array, int len , int n ) {
   //count to store pairs
    int cnt = 0;
   //storing strings with wildcard characters
    map<string, int> pattern;
   //storing equivalent strings
    map<string, int> similar;
   //iterating over the array
   for (auto str : array) {
      //if two strings are same , increment the count
       similar[str]+= 1;
 
      // Iterating on a single string
       for (int i = 0; i < len ; i++) {
      // Adding special symbol to the string
       string first = str.substr(0, i);
       string second = str.substr(i + 1);
       string temp =  first + "//" + second ;
 
      //incrementing if similar pattern 
        pattern[temp]+=1;
      }
   }
 
   // Return counted pairs - equal pairs
   int chnged = countPairs(pattern);
   int sim = countPairs(similar);
   cnt =  chnged - sim * len;
   cout << "The count of pairs satisfying the condition are : " << cnt; 
}
 
//calling the main method
int main() {
   int n = 4, len = 3;
   //getting a vector of strings to process
   vector<string> strings = {"get","set","bet","bat"};
   cout << "Vector of strings : " << "\n" ;
   for(auto s : strings){
       cout << s <<"\n";
   }
   //one character different
   chardiff(strings, len , n );
 
   return 0;
}

Output

Vector of strings − 
get
set
bet
bat
The count of pairs satisfying the condition are − 4

in conclusion

Maps simulates the process of record insertion and update with O(1) time complexity. The substring method in C can be used to access the characters of a string in order between specified indices. The product of n and n-1 divided by 2 gives the sum of any number of pairs.

The above is the detailed content of Count the number of pairs of strings that differ in only one position. For more information, please follow other related articles on the PHP Chinese website!