Given two strings S1 and S2, the task is to check if string S1 can be made equal to string S2 by swapping any pair of characters replacing any character in the string S1. If it is possible to make the string S1 equal to S2, then print “Yes”. Otherwise, print “No”.
Examples:
Input: S1 = “abc”, S2 = “bca”
Output: Yes
Explanation:
Operation 1: “abc” -> “acb”
Operation 2: “acb” -> “bca”Input: S1 = “a”, S2 = “aa”
Output: No
Explanation: It is impossible to make the two strings same.
Approach: The idea to solve this problem is to find the frequencies of the characters in the strings and check that the same character is being used in both strings or not. Follow the steps below to solve the problem:
- Initialize two arrays a[] and b[] to store the frequencies of the strings S1 and S2.
- Traverse both the strings S1 and S2 and store the frequencies of strings in the arrays a[] and b[].
- Sort both the arrays a[] and b[].
- Traverse both the arrays and if any element is unequal at any index then print “No” as there is at least one character that is different in both the strings.
- After the above steps if there doesn’t exist any unequal frequency then print “Yes” as the string S1 can be converted to string S2 with the given operations.
Below is the implementation of this approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find if given strings// are same or notbool sameStrings(string str1, string str2){ int N = str1.length(); int M = str2.length(); // Base Condition if (N != M) { return false; } // Stores frequency of characters // of the string str1 and str2 int a[256] = { 0 }, b[256] = { 0 }; // Traverse strings str1 & str2 and // store frequencies in a[] and b[] for (int i = 0; i < N; i++) { a[str1[i] - 'a']++; b[str2[i] - 'a']++; } // Check if both strings have // same characters or not int i = 0; while (i < 256) { if ((a[i] == 0 && b[i] == 0) || (a[i] != 0 && b[i] != 0)) { i++; } // If a character is present // in one string and is not in // another string, return false else { return false; } } // Sort the array a[] and b[] sort(a, a + 256); sort(b, b + 256); // Check arrays a and b contain // the same frequency or not for (int i = 0; i < 256; i++) { // If the frequencies are not // the same after sorting if (a[i] != b[i]) return false; } // At this point, str1 can // be converted to str2 return true;}// Driver Codeint main(){ string S1 = "cabbba", S2 = "abbccc"; if (sameStrings(S1, S2)) cout << "YES" << endl; else cout << " NO" << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find if given Strings// are same or notstatic boolean sameStrings(String str1, String str2){ int N = str1.length(); int M = str2.length(); // Base Condition if (N != M) { return false; } // Stores frequency of characters // of the String str1 and str2 int []a = new int[256]; int []b = new int[256]; // Traverse Strings str1 & str2 and // store frequencies in a[] and b[] for (int i = 0; i < N; i++) { a[str1.charAt(i) - 'a']++; b[str2.charAt(i) - 'a']++; } // Check if both Strings have // same characters or not int i = 0; while (i < 256) { if ((a[i] == 0 && b[i] == 0) || (a[i] != 0 && b[i] != 0)) { i++; } // If a character is present // in one String and is not in // another String, return false else { return false; } } // Sort the array a[] and b[] Arrays.sort(a); Arrays.sort(b); // Check arrays a and b contain // the same frequency or not for (i = 0; i < 256; i++) { // If the frequencies are not // the same after sorting if (a[i] != b[i]) return false; } // At this point, str1 can // be converted to str2 return true;} // Driver Codepublic static void main(String[] args){ String S1 = "cabbba", S2 = "abbccc"; if (sameStrings(S1, S2)) System.out.print("YES" +"\n"); else System.out.print(" NO" +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find if given strings# are same or notdef sameStrings(str1, str2): N = len(str1) M = len(str2) # Base Condition if (N != M): return False # Stores frequency of characters # of the str1 and str2 a, b = [0]*256, [0]*256 # Traverse strings str1 & str2 and # store frequencies in a[] and b[] for i in range(N): a[ord(str1[i]) - ord('a')] += 1 b[ord(str2[i]) - ord('a')] += 1 # Check if both strings have # same characters or not i = 0 while (i < 256): if ((a[i] == 0 and b[i] == 0) or (a[i] != 0 and b[i] != 0)): i += 1 # If a character is present # in one and is not in # another string, return false else: return False # Sort the array a[] and b[] a = sorted(a) b = sorted(b) # Check arrays a and b contain # the same frequency or not for i in range(256): # If the frequencies are not # the same after sorting if (a[i] != b[i]): return False # At this point, str1 can # be converted to str2 return True # Driver Codeif __name__ == '__main__': S1, S2 = "cabbba", "abbccc" if (sameStrings(S1, S2)): print("YES") else: print("NO")# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function to find if given Strings// are same or notstatic bool sameStrings(string str1, string str2){ int N = str1.Length; int M = str2.Length; // Base Condition if (N != M) { return false; } // Stores frequency of characters // of the String str1 and str2 int []a = new int[256]; int []b = new int[256]; // Traverse Strings str1 & str2 and // store frequencies in a[] and b[] for (int j = 0; j < N; j++) { a[str1[j] - 'a']++; b[str2[j] - 'a']++; } // Check if both Strings have // same characters or not int i = 0 ; while (i < 256) { if ((a[i] == 0 && b[i] == 0) || (a[i] != 0 && b[i] != 0)) { i++; } // If a character is present // in one String and is not in // another String, return false else { return false; } } // Sort the array a[] and b[] Array.Sort(a); Array.Sort(b); // Check arrays a and b contain // the same frequency or not for (int j = 0; j < 256; j++) { // If the frequencies are not // the same after sorting if (a[j] != b[j]) return false; } // At this point, str1 can // be converted to str2 return true;} // Driver Code static public void Main() { string S1 = "cabbba", S2 = "abbccc"; if (sameStrings(S1, S2)) Console.Write("YES" +"\n"); else Console.Write(" NO" +"\n"); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript program for the above approach // Function to find if given Strings // are same or not function sameStrings(str1, str2) { var N = str1.length; var M = str2.length; // Base Condition if (N !== M) { return false; } // Stores frequency of characters // of the String str1 and str2 var a = new Array(256).fill(0); var b = new Array(256).fill(0); // Traverse Strings str1 & str2 and // store frequencies in a[] and b[] for (var j = 0; j < N; j++) { a[str1[j].charCodeAt(0) - "a".charCodeAt(0)]++; b[str2[j].charCodeAt(0) - "a".charCodeAt(0)]++; } // Check if both Strings have // same characters or not var i = 0; while (i < 256) { if ((a[i] === 0 && b[i] === 0) || (a[i] !== 0 && b[i] !== 0)) { i++; } // If a character is present // in one String and is not in // another String, return false else { return false; } } // Sort the array a[] and b[] a.sort((x, y) => x - y); b.sort((x, y) => x - y); // Check arrays a and b contain // the same frequency or not for (var j = 0; j < 256; j++) { // If the frequencies are not // the same after sorting if (a[j] !== b[j]) return false; } // At this point, str1 can // be converted to str2 return true; } // Driver Code var S1 = "cabbba", S2 = "abbccc"; if (sameStrings(S1, S2)) document.write("YES" + "<br>"); else document.write(" NO" + "<br>"); </script> |
Output:
YES
Time Complexity: O(N)
Auxiliary Space: O(256)
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!
