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 swaplong 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 Codeint main(){ string S = "geek"; // Function Call long long ans = countStrings(S); cout << ans << endl; return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class GFG{ // Function to count number of distinct// string formed after one swapstatic 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 codepublic 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 swapdef 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 codeif __name__ == '__main__': S = "geek"; # Function Call ans = countStrings(S); print(ans);# This code is contributed by 29AjayKumar |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to count number of distinct// string formed after one swapstatic 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 codepublic 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 swapfunction 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 Codelet S = "geek";// Function Calllet ans = countStrings(S);document.write(ans + '<br>')// This code is contributed by Potta Lokesh</script> |
Output
6
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.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
