Count of distinct Strings possible by swapping prefixes of pairs of Strings from the Array

0 0 4 minutes read

Given an array string[] consisting of N numeric strings of length M, the task is to find the number of distinct strings that can be generated by selecting any two strings, say i and j from the array and swap all possible prefixes between them.
Note: Since the answer can be very large, print modulo 1000000007.

Examples:

Input: N = 2 M = 3 string[] = {“112”, “211”}
Output: 4
Explanation:
Swapping “1” and “2” between the strings generates “212” and “111“.
Swapping “11” and “21” between the strings generates “212” and “111”.
Swapping “112” and “211” between the strings generates “211” and “112“.
Therefore, 4 distinct strings are generated.

Input: N = 4 M = 5 string[] = {“12121”, “23545”, “11111”, “71261”}
Output: 216

Approach: Considering a string s of the form s₁s₂s₃s₄…s_m, where s₁ is the first letter of any of the strings in the array, s₂ is the second letter of any of the strings, and so on, the answer to the problem is the product of count(i) where count(i) is the count of different letters placed at same index in the given strings.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>   
using namespace std; 
 
int mod = 1000000007;
 
// Function to count the distinct strings
// possible after swapping the prefixes
// between two possible strings of the array
long countS(string str[],int n, int m)
{
     
    // Stores the count of unique
    // characters for each index
    unordered_map<int, 
    unordered_set<char>> counts;
 
    for(int i = 0; i < n; i++) 
    {
         
        // Store current string
        string s = str[i];
     
        for(int j = 0; j < m; j++)
        {
            counts[j].insert(s[j]);
        }
    }
 
    // Stores the total number of
    // distinct strings possible
    long result = 1;
     
    for(auto index : counts)
    {
        result = (result * 
                  counts[index.first].size()) % mod;
    }
     
    // Return the answer
    return result;
}
 
// Driver Code
int main()
{
    string str[] = { "112", "211" };
 
    int N = 2, M = 3;
     
    cout << countS(str, N, M);
     
    return 0;
} 
 
// This code is contributed by rutvik_56

Java

// Java Program to implement
// the above approach
import java.util.*;
import java.io.*;
 
public class Main {
 
    static int mod = 1000000007;
 
    // Function to count the distinct strings
    // possible after swapping the prefixes
    // between two possible strings of the array
    public static long countS(String str[], int n, int m)
    {
 
        // Stores the count of unique
        // characters for each index
        Map<Integer, Set<Character> > counts
            = new HashMap<>();
 
        for (int i = 0; i < m; i++) {
            counts.put(i, new HashSet<>());
        }
 
        for (int i = 0; i < n; i++) {
 
            // Store current string
            String s = str[i];
 
            for (int j = 0; j < m; j++) {
                counts.get(j).add(s.charAt(j));
            }
        }
 
        // Stores the total number of
        // distinct strings possible
        long result = 1;
 
        for (int index : counts.keySet())
            result = (result
                    * counts.get(index).size())
                    % mod;
 
        // Return the answer
        return result;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        String str[] = { "112", "211" };
 
        int N = 2, M = 3;
        System.out.println(countS(str, N, M));
    }
}

Python3

# Python3 program to implement
# the above approach
from collections import defaultdict
 
mod = 1000000007
 
# Function to count the distinct strings
# possible after swapping the prefixes
# between two possible strings of the array
def countS(string: list, n: int, m: int) -> int:
     
    # Stores the count of unique
    # characters for each index
    counts = defaultdict(lambda: set())
 
    for i in range(n):
         
        # Store current string
        s = string[i]
 
        for j in range(m):
            counts[j].add(s[j])
 
    # Stores the total number of
    # distinct strings possible
    result = 1
 
    for index in counts:
        result = (result *
                  len(counts[index])) % mod
 
    # Return the answer
    return result
 
# Driver Code
if __name__ == "__main__":
     
    string = [ "112", "211" ]
 
    N = 2
    M = 3
     
    print(countS(string, N, M))
 
# This code is contributed by sanjeev2552

C#

// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
static int mod = 1000000007;
 
// Function to count the distinct strings
// possible after swapping the prefixes
// between two possible strings of the array
public static long countS(String []str,
                            int n, int m)
{
 
    // Stores the count of unique
    // characters for each index
    Dictionary<int, 
    HashSet<char> > counts = new Dictionary<int, 
                                    HashSet<char>>();
 
    for (int i = 0; i < m; i++)
    {
    counts.Add(i, new HashSet<char>());
    }
 
    for (int i = 0; i < n; i++) 
    {
 
    // Store current string
    String s = str[i];
 
    for (int j = 0; j < m; j++)
    {
        counts[j].Add(s[j]);
    }
    }
 
    // Stores the total number of
    // distinct strings possible
    long result = 1;
 
    foreach (int index in counts.Keys)
    result = (result * counts[index].Count) % mod;
 
    // Return the answer
    return result;
}
 
// Driver Code
public static void Main(String[] args)
{
    String []str = { "112", "211" };
 
    int N = 2, M = 3;
    Console.WriteLine(countS(str, N, M));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

// Javascript Program to implement
// the above approach
let mod = 1000000007;
 
// Function to count the distinct strings
// possible after swapping the prefixes
// between two possible strings of the array
function countS(str, n, m) {
 
    // Stores the count of unique
    // characters for each index
    let counts = new Map();
 
    for (let i = 0; i < m; i++) {
        counts.set(i, new Set());
    }
 
    for (let i = 0; i < n; i++) {
 
        // Store current string
        let s = str[i];
 
        for (let j = 0; j < m; j++) {
            let temp = counts.get(j);
            temp.add(s[j])
        }
    }
 
    // Stores the total number of
    // distinct strings possible
    let result = 1;
 
    for (let index of counts.keys())
        result = (result * counts.get(index).size) % mod;
 
    // Return the answer
    return result;
}
 
// Driver Code
 
let str = ["112", "211"];
 
let N = 2, M = 3;
console.log(countS(str, N, M));
 
// This code is contributed by saurabh_jaiswal.

Output:

Time Complexity: O(N * M)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!