Check if number of distinct characters in 2 Strings can be made equal
Given two strings A and B of lowercase English letters of lengths N and M respectively. Check whether the number of distinct characters in both strings A and B can be made equal by applying the operation at most one time. Where operation is:
- Choose any index i such that 0 ≤ i ≤ N from string A and index j such that 0<=j<=M from string B.
- Swap the characters present on A[i] and B[j].
Examples:
Input: A= “nascars”, B=”w3wiki”
Output: YES
Explanation: Initially String A has 5 distinct characters (n, a, s, c, and r), and String B has 7 distinct characters (g, e, k, s, f, o, and r). If we swap i = 2 from String A to j=5 from string B, the resulting String will be, A = “nafcars” and B = “BeginnersorBeginner”Now, both strings A and B have 6 distinct characters.
- Distinct characters of string A are n, a, f, c, r, and s.
- Distinct characters of string B are g, e, k, s, o, and r.
Input: A = “gap”, B = “cap”
Output: YES
Explanation: Both strings already have the same number of distinct characters i.e. 3.Input: A = “old”, B = “o”
Output: NO
Explanation: No possible swapping between indexes of both strings can make the count of distinct characters equal.
Approach: This can be solved with the following idea:
Instead of swapping indexes between both strings, we can try swapping each character from English alphabet if possible from String A and B using the Map. If at any point their size equals then we can certainly make the count of their distinct character equal.
Steps involved in the implementation of code:
- We initialize two maps named a and b, keeping the frequency of characters of String A and String B respectively.
- Then we run two loops from i = 0 to 26 and j = 0 to 26, to create the all possible pairs of lowercase English alphabets.
- We make sure that both the characters of pairs are present in their respective maps.
- After swapping the characters from one map to another, We make the comparison of their map size and check if their size of Map is equal or not.
- After checking for their size, we again transform the maps back to their original form.
Below is the code for implementation of code:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Driver code int main() { string A = "nascars" ; string B = "w3wiki" ; // Using Map to Store the frequency of // characters present in string A and B. map< char , int > a, b; // Storing every character present in // both strings in their respective map for ( int i = 0; i < A.size(); i++) a[A[i]]++; for ( int i = 0; i < B.size(); i++) b[B[i]]++; // Checking if both string's distinct // character count is already equal // without applying the operation. if (a.size() == b.size()) printf ( "YES" ); else { bool flag = false ; // For selecting all indexes // from string A for ( int i = 0; i < 26; i++) { char s = 'a' + i; for ( int j = 0; j < 26; j++) { char t = 'a' + j; // Checking if both characters // s and t are present in // their respective map if (a.find(s) != a.end() && b.find(t) != b.end()) { // Now, we swap the // character and compare // the size of both maps. // We delete the character // s from Map a and give // it to Map b. and delete // character t from // Map b and give it // to Map a. // If the character s // has only one occurrence // then we delete the // character else we // decrease the frequncy // by 1 in Map a. if (a[s] - 1 == 0) a.erase(s); else a[s]--; // Adding character // s in Map b. b[s]++; // If the character t // has only one occurrence // then we delete the // character else we // decrease the frequncy // by 1 in Map b. if (b[t] - 1 == 0) b.erase(t); else b[t]--; // Adding character t // in Map a. a[t]++; // After swapping, we // check their size of map. // If true then we can have // the condition fulfilled. if (a.size() == b.size()) { flag = true ; } // To keep this going // we again go back in the // previous state after // checking for characters // s and t. // Deleting the character // t from map A that // we added if (a[t] - 1 == 0) a.erase(t); else a[t]--; // Adding the character // t back to the Map b. b[t]++; // Deleting the character // s from map b that // we added if (b[s] - 1 == 0) b.erase(s); else b[s]--; // Adding the character // s back to the Map a. a[s]++; } } } // Print yes, If we managed to // find such pair else no. if (flag) printf ( "YES" ); else printf ( "NO" ); } } |
Java
// Java implementation of the approach import java.io.*; import java.util.*; class GFG { public static void main(String[] args) { String A = "nascars" ; String B = "w3wiki" ; // Using Map to Store the frequency of characters // present in string A and B. Map<Character, Integer> a = new HashMap<>(); Map<Character, Integer> b = new HashMap<>(); // Storing every character present in both strings // in their respective map for ( int i = 0 ; i < A.length(); i++) { char c = A.charAt(i); a.put(c, a.getOrDefault(c, 0 ) + 1 ); } for ( int i = 0 ; i < B.length(); i++) { char c = B.charAt(i); b.put(c, b.getOrDefault(c, 0 ) + 1 ); } // Checking if both string's distinct character // count is already equal without applying the // operation. if (a.size() == b.size()) { System.out.println( "YES" ); } else { boolean flag = false ; // For selecting all indexes from string A for ( int i = 0 ; i < 26 ; i++) { char s = ( char )( 'a' + i); for ( int j = 0 ; j < 26 ; j++) { char t = ( char )( 'a' + j); // Checking if both characters s and t // are present in their respective map if (a.containsKey(s) && b.containsKey(t)) { // Now, we swap the character and // compare the size of both maps. // We delete the character s from // Map a and give it to Map b. and // delete character t from Map b and // give it to Map a. // If the character s has only one // occurrence then we delete the // character else we decrease the // frequncy by 1 in Map a. if (a.get(s) - 1 == 0 ) { a.remove(s); } else { a.put(s, a.get(s) - 1 ); } // Adding character s in Map b. b.put(s, b.getOrDefault(s, 0 ) + 1 ); // If the character t has only one // occurrence then we delete the // character else we decrease the // frequncy by 1 in Map b. if (b.get(t) - 1 == 0 ) { b.remove(t); } else { b.put(t, b.get(t) - 1 ); } // Adding character t in Map a. a.put(t, a.getOrDefault(t, 0 ) + 1 ); // After swapping, we check their // size of map. If true then we can // have the condition fulfilled. if (a.size() == b.size()) { flag = true ; } // To keep this going we again go // back in the previous state after // checking for characters s and t. // Deleting the character t from map // A that we added if (a.get(t) - 1 == 0 ) { a.remove(t); } else { a.put(t, a.get(t) - 1 ); } // Adding the character t back to // the Map b. b.put(t, b.getOrDefault(t, 0 ) + 1 ); // Deleting the character s from map // b that we added if (b.get(s) - 1 == 0 ) { b.remove(s); } else { b.put(s, b.get(s) - 1 ); } // Adding the character s back to // the Map a. a.put(s, a.getOrDefault(s, 0 ) + 1 ); } } } // Print yes, If we managed to find such pair // else no. if (flag) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } } } // This code is contributed by karthik |
Python3
# Python implementation of the approach # Using Map to Store the frequency of # characters present in string A and B. a = {} b = {} # Storing every character present in # both strings in their respective map A = "nascars" B = "w3wiki" for i in range ( len (A)): c = A[i] a = a.get(c, 0 ) + 1 for i in range ( len (B)): c = B[i] b = b.get(c, 0 ) + 1 # Checking if both string's distinct character count is # already equal without applying the operation. if len (a) = = len (b): print ( "YES" ) else : flag = False # For selecting all indexes from string A for i in range ( 26 ): s = chr ( ord ( 'a' ) + i) for j in range ( 26 ): t = chr ( ord ( 'a' ) + j) # Checking if both characters s and t are present # in their respective map if s in a and t in b: # Now, we swap the character and compare the size of # both maps. # We delete the character s from Map a and give it # to Map b. and delete character t from Map b and give # it to Map a. # If the character s has only one occurrence then we # delete the character else we decrease the frequncy # by 1 in Map a. if a.get(s) - 1 = = 0 : del a[s] else : a[s] = a.get(s) - 1 # Adding character s in Map b. b[s] = b.get(s, 0 ) + 1 # If the character t has only one occurrence then we # delete the character else we decrease the frequncy # by 1 in Map b. if b.get(t) - 1 = = 0 : del b[t] else : b[t] = b.get(t) - 1 # Adding character t in Map a. a[t] = a.get(t, 0 ) + 1 # After swapping, we check their size of map. If true # then we can have the condition fulfilled. if len (a) = = len (b): flag = True # To keep this going we again go back in the previous # state after checking for characters s and t. # Deleting the character t from map A that we added if a.get(t) - 1 = = 0 : del a[t] else : a[t] = a.get(t) - 1 # Adding the character t back to the Map b. b[t] = b.get(t, 0 ) + 1 # Deleting the character s from map b that we added if b.get(s) - 1 = = 0 : del b[s] else : b[s] = b.get(s) - 1 # Adding the character s back to the Map a. a[s] = a.get(s, 0 ) + 1 # Print yes, If we managed to find such pair else no. if (flag): print ( "YES" ) else : print ( "NO" ) # This code is contributed by karthik. |
C#
// C# implementation of the approach using System; using System.Collections.Generic; public class GFG { static public void Main() { // Code string A = "nascars" ; string B = "w3wiki" ; // Using Dictionary to Store the frequency of // characters present in string A and B. Dictionary< char , int > a = new Dictionary< char , int >(); Dictionary< char , int > b = new Dictionary< char , int >(); // Storing every character present in both strings // in their respective dictionary for ( int i = 0; i < A.Length; i++) { char c = A[i]; if (a.ContainsKey(c)) { a++; } else { a = 1; } } for ( int i = 0; i < B.Length; i++) { char c = B[i]; if (b.ContainsKey(c)) { b++; } else { b = 1; } } // Checking if both string's distinct character // count is already equal without applying the // operation. if (a.Count == b.Count) { Console.WriteLine( "YES" ); } else { bool flag = false ; // For selecting all indexes from string A for ( int i = 0; i < 26; i++) { char s = ( char )( 'a' + i); for ( int j = 0; j < 26; j++) { char t = ( char )( 'a' + j); // Checking if both characters s and t // are present in their respective // dictionary if (a.ContainsKey(s) && b.ContainsKey(t)) { // Now, we swap the character and // compare the size of both // dictionaries. // We delete the character s from // Dictionary a and give it to // Dictionary b. and delete // character t from Dictionary b and // give it to Dictionary a. // If the character s has only one // occurrence then we delete the // character else we decrease the // frequency by 1 in Dictionary a. if (a[s] - 1 == 0) { a.Remove(s); } else { a[s]--; } // Adding character s in Dictionary // b. if (b.ContainsKey(s)) { b[s]++; } else { b[s] = 1; } // If the character t has only one // occurrence then we delete the // character else we decrease the // frequency by 1 in Dictionary b. if (b[t] - 1 == 0) { b.Remove(t); } else { b[t]--; } // Adding character t in Dictionary // a. if (a.ContainsKey(t)) { a[t]++; } else { a[t] = 1; } // After swapping, we check their // size of dictionary. If true then // we can have the condition // fulfilled. if (a.Count == b.Count) { flag = true ; } // To keep this going we again go // back in the previous state after // checking for characters s and t. // Deleting the character t from // dictionary A that we added if (a[t] - 1 == 0) { a.Remove(t); } else { a[t] = a[t] - 1; } // Adding the character t back to // the Map b. b[t] = b.ContainsKey(t) ? b[t] + 1 : 1; // Deleting the character s from map // b that we added if (b[s] - 1 == 0) { b.Remove(s); } else { b[s] = b[s] - 1; } // Adding the character s back to // the Map a. a[s] = a.ContainsKey(s) ? a[s] + 1 : 1; } } } // Print yes, If we managed to find such pair // else no. if (flag) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } } // This code is contributed by lokesh. |
Javascript
//JavaScript implementation of the approach // Driver code function main() { const A = "nascars" ; const B = "w3wiki" ; // Using Map to Store the frequency of // characters present in string A and B. const a = new Map(); const b = new Map(); // Storing every character present in // both strings in their respective map for (let i = 0; i < A.length; i++) a.set(A[i], a.get(A[i]) + 1 || 1); for (let i = 0; i < B.length; i++) b.set(B[i], b.get(B[i]) + 1 || 1); // Checking if both string's distinct // character count is already equal // without applying the operation. if (a.size === b.size) console.log( "YES" ); else { let flag = false ; // For selecting all indexes // from string A for (let i = 0; i < 26; i++) { const s = String.fromCharCode(97 + i); for (let j = 0; j < 26; j++) { const t = String.fromCharCode(97 + j); // Checking if both characters // s and t are present in // their respective map if (a.has(s) && b.has(t)) { // Now, we swap the // character and compare // the size of both maps. // We delete the character // s from Map a and give // it to Map b. and delete // character t from // Map b and give it // to Map a. // If the character s // has only one occurrence // then we delete the // character else we // decrease the frequncy // by 1 in Map a. if (a.get(s) - 1 === 0) a. delete (s); else a.set(s, a.get(s) - 1); // Adding character // s in Map b. b.set(s, b.get(s) + 1); // If the character t // has only one occurrence // then we delete the // character else we // decrease the frequncy // by 1 in Map b. if (b.get(t) - 1 === 0) b. delete (t); else b.set(t, b.get(t) - 1); // Adding character t // in Map a. a.set(t, a.get(t) + 1); // After swapping, we // check their size of map. // If true then we can have // the condition fulfilled. if (a.size === b.size) { flag = true ; } // To keep this going // we again go back in the // previous state after // checking for characters // s and t. // Deleting the character // t from map A that // we added if (a.get(t) - 1 === 0) a. delete (t); else a.set(t, a.get(t) - 1); // Adding the character // t back to the Map b b.set(t, b.get(t) + 1); // Deleting the character // s from map b that // we added if (b.get(s) - 1 === 0) b. delete (s); else b.set(s, b.get(s) - 1); // Adding the character // s back to the Map a. a.set(s, a.get(s) + 1); } } } // Print yes, If we managed to // find such pair else no. if (flag) console.log( "YES" ); else console.log( "NO" ); } } main(); |
YES
Time Complexity: O(26*26)
Auxiliary Space: O(N+M), N is the length of String A and M is the length of String B.