Count of distinct strings that can be obtained after performing exactly one swap

0 0 4 minutes read

Given a string s containing lowercase English alphabet characters. The task is to calculate the number of distinct strings that can be obtained after performing exactly one swap.

Input: s = “geek”
Output: 6
Explanation: Following are the strings formed by doing exactly one swap
strings = [“egek”,”eegk”,”geek”,”geke”,”gkee”, “keeg”]Therefore, there are 6 distinct possible strings.

Input: s = “ab”
Output: 1

Approach: This problem can be solved by using HashMaps. Follow the steps below to solve the given problem.

Check for the number of unique elements in the string s.
Store the frequencies of all the unique characters in a map.
Declare a variable say ans = 0, to store the number of distinct possible strings.
Iterate over the string and increment ans by no of elements apart from the current element which will be used to construct a new string.
Iterate over the string again and check if the frequency of some characters is greater than 2. If so then increment answer by 1 as they will be forming only one extra unique string.
Return ans as the final answer.

Below is the implementation of the above approach

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of distinct
// string formed after one swap
long long countStrings(string S)
{
    long long N = S.size();
 
    // mp[] to store the frequency 
    // of each character
    int mp[26] = { 0 };
 
    // For storing frequencies
    for (auto i : S) {
        mp[i - 'a']++;
    }
    long long ans = 0;
    for (auto i : S) {
        ans += N - mp[i - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    string S = "geek";
 
    // Function Call
    long long ans = countStrings(S);
    cout << ans << endl;
 
    return 0;
}

Java

// Java code to implement the above approach
import java.util.*;
public class GFG
{
   
// Function to count number of distinct
// string formed after one swap
static long countStrings(String S)
{
    long N = S.length();
 
    // mp[] to store the frequency 
    // of each character
    int mp[] = new int[26];
    for(int i = 0; i < 26; i++) {
        mp[i] = 0;
    }
 
    // For storing frequencies
    for (int i = 0; i < S.length(); i++) {
        mp[S.charAt(i) - 'a']++;
    }
    long ans = 0;
    for (int i = 0; i < S.length(); i++) {
        ans += N - mp[S.charAt(i) - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    String S = "geek";
 
    // Function Call
    long ans = countStrings(S);
    System.out.println(ans);
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code to implement the above approach
 
# Function to count number of distinct
# string formed after one swap
def countStrings(S):
    N = len(S);
 
    # mp to store the frequency
    # of each character
    mp = [0 for i in range(26)];
    for i in range(26):
        mp[i] = 0;
 
    # For storing frequencies
    for i in range(N):
        mp[ord(S[i]) - ord('a')] += 1;
 
    ans = 0;
    for i in range(N):
        ans += N - mp[ord(S[i]) - ord('a')];
 
    ans //= 2;
 
    for i in range(26):
        if (mp[i] >= 2):
            ans += 1;
            break;
 
    return ans;
 
# Driver code
if __name__ == '__main__':
    S = "geek";
 
    # Function Call
    ans = countStrings(S);
    print(ans);
 
# This code is contributed by 29AjayKumar

C#

// C# code to implement the above approach
using System;
class GFG
{
   
// Function to count number of distinct
// string formed after one swap
static long countStrings(string S)
{
    long N = S.Length;
 
    // mp[] to store the frequency 
    // of each character
    int []mp = new int[26];
    for(int i = 0; i < 26; i++) {
        mp[i] = 0;
    }
 
    // For storing frequencies
    for (int i = 0; i < S.Length; i++) {
        mp[S[i] - 'a']++;
    }
    long ans = 0;
    for (int i = 0; i < S.Length; i++) {
        ans += N - mp[S[i] - 'a'];
    }
    ans /= 2;
 
    for (int i = 0; i < 26; i++) {
        if (mp[i] >= 2) {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver code
public static void Main()
{
    string S = "geek";
 
    // Function Call
    long ans = countStrings(S);
    Console.Write(ans);
}
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
// JavaScript program for above approach 
 
// Function to count number of distinct
// string formed after one swap
function countStrings(S) 
{
    let N = S.length;
 
    // mp[] to store the frequency 
    // of each character
    let mp = new Map();
 
    // For storing frequencies
    for(let i = 0; i < S.length; i++)
    {
        if (!mp.has(S[i].charCodeAt(0) - 'a'.charCodeAt(0)))
        {
            mp.set(S[i].charCodeAt(0) - 'a'.charCodeAt(0), 1);
        }
        else
        {
            mp.set(S[i].charCodeAt(0) - 
                    'a'.charCodeAt(0), 
                   mp.get(S[i].charCodeAt(0) - 
                           'a'.charCodeAt(0)) + 1)
        }
    }
    let ans = 0;
    for(let i = 0; i < S.length; i++)
    {
        ans += N - mp.get(S[i].charCodeAt(0) - 
                           'a'.charCodeAt(0));
    }
    ans = Math.floor(ans / 2)
 
    for(let i = 0; i < 26; i++) 
    {
        if (mp.get(i) >= 2)
        {
            ans++;
            break;
        }
    }
    return ans;
}
 
// Driver Code
let S = "geek";
 
// Function Call
let ans = countStrings(S);
document.write(ans + '<br>')
 
// This code is contributed by Potta Lokesh
 
</script>

Output

Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time.
Auxiliary Space: O(1), as we are not using any extra space.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!