The number of string pairs that differ by exactly one position



Examples :

Input: arr [] = {“abc”, “abd”, “bbd”}
Output: 2
(abc, abd) and (abd, bbd) are the only valid pairs.

Input: arr [] = {“Def”, “deg”, “dmf”, “xef”, “dxg”}
Output: 4

Method 1: For each possible pair, check if both strings differ at exactly the same index position with one row traversal.

Method 2: two strings can be compare as follows to check if they differ at the same index position:

Let str1 = “abc” and str2 = “adc”
For str1 , add “#bc” , “a # c” and “ab #” to a set .
Now for str2 , generate the string in the similar manner and if any of the generated string
is already present in the set then both the strings differ in exactly 1 index position.
For example, “a # c” is one of the generated strings.
Note that “#” is used because it will not be a part of any of the original strings.

Below is the implementation of the above approach:

# Python3 implementation of the approach

 
# Function to return the number of identical pairs

def pair_count (d):

return sum ((i * (i - 1 )) / / 2 for i in d.values ​​())

 

  
# Function to return the total number of lines
# that meet the required condition

def Difference (array, m):

 

# Dictionary changed to store strings

# with wildcards

# The dictionary will store strings

  # which are equal

  changed, same = {}, {}

 

# Iterate for all rows in a given array

for s in array:

  

# If we find a line, we increase it by 1

# Otherwise it will default to 0

  same [s] = same.get (s , 0 ) + 1

 

# Iterate one line at a time

for i in range (m):

# Add a special character to the string

t = s [: i ] + `#` + s [i + 1 :]

 

# Increase line if found

 

# Otherwise it will default to 0

  changed [t] = changed.get (t , 0 ) + 1

  

  # Return counted pairs - equal pairs

return pair_count (changed) - pair_count (same) * m

  
# Driver code

if __ name__ = = "__ main__" :

n, m = 3 , 3

array = [ "abc" , "abd" , "bbd" ]

print (Difference (array, m))

Exit :

 2