Given two strings str1 and str2, the task is to check if a string str1 can be converted to string str2 by performing the following operations any number of times:
- Swap any two characters of str1.
- Swap all the occurrences of a character of str1 to all occurrences of any other distinct character of str1.
Examples:
Input: str1 = “xyyzzlll”, str2 = “yllzzxxx”
Output: True
Explanation:
Swap all occurrences of str1[0] and str1[1] modifies str1 to “yxxzzlll”
Swap all occurrences of str1[1] and str1[5] modifies str1 to “yllzzxxx”
Since str1 and str2 are equal, therefore, the required output is True.Input: str1 = “xyyzzavl”, str2 = “yllzzvac”
Output: False
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Initialize two arrays, say hash1[256] and hash2[256] to store the frequency of each distinct element of str1 and str2 respectively.
- Initialize two sets, say st1 and st2 to store the distinct characters of str1 and str2.
- Traverse the string and store the frequency of each distinct character of str1 and str2.
- Sort hash1[] and hash2[] array.
- If st1 and st2 are not equal then print false.
- Traverse hash1[] and hash2[] array using variable i and check if the value of (hash1[i] != hash2[i]) is true or not. If found to be true then print False.
- Otherwise, print True.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;bool checkStr1CanConStr2(string& str1, string& str2){ // Stores length of str1 int N = str1.length(); // Stores length of str2 int M = str2.length(); // Stores distinct characters // of str1 set<int> st1; // Stores distinct characters // of str2 set<int> st2; // Stores frequency of // each character of str1 int hash1[256] = { 0 }; // Traverse the string str1 for (int i = 0; i < N; i++) { // Update frequency // of str1[i] hash1[str1[i]]++; } // Traverse the string str1 for (int i = 0; i < N; i++) { // Insert str1[i] // into st1 st1.insert(str1[i]); } // Traverse the string str2 for (int i = 0; i < M; i++) { // Insert str1[i] // into st1 st2.insert(str2[i]); } // If distinct characters in // str1 and str2 are not same if (st1 != st2) { return false; } // Stores frequency of // each character of str2 int hash2[256] = { 0 }; // Traverse the string str2 for (int i = 0; i < M; i++) { // Update frequency // of str2[i] hash2[str2[i]]++; } // Sort hash1[] array sort(hash1, hash1 + 256); // Sort hash2[] array sort(hash2, hash2 + 256); // Traverse hash1[] and hash2[] for (int i = 0; i < 256; i++) { // If hash1[i] not // equal to hash2[i] if (hash1[i] != hash2[i]) { return false; } } return true;}// Driver Codeint main(){ string str1 = "xyyzzlll"; string str2 = "yllzzxxx"; if (checkStr1CanConStr2(str1, str2)) { cout << "True"; } else { cout << "False"; }} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static boolean checkStr1CanConStr2(String str1, String str2){ // Stores length of str1 int N = str1.length(); // Stores length of str2 int M = str2.length(); // Stores distinct characters // of str1 HashSet<Integer> st1 = new HashSet<>(); // Stores distinct characters // of str2 HashSet<Integer> st2 = new HashSet<>(); // Stores frequency of // each character of str1 int hash1[] = new int[256]; // Traverse the String str1 for (int i = 0; i < N; i++) { // Update frequency // of str1[i] hash1[str1.charAt(i)]++; } // Traverse the String str1 for (int i = 0; i < N; i++) { // Insert str1[i] // into st1 st1.add((int)str1.charAt(i)); } // Traverse the String str2 for (int i = 0; i < M; i++) { // Insert str1[i] // into st1 st2.add((int)str2.charAt(i)); } // If distinct characters in // str1 and str2 are not same if (!st1.equals(st2)) { return false; } // Stores frequency of // each character of str2 int hash2[] = new int[256]; // Traverse the String str2 for (int i = 0; i < M; i++) { // Update frequency // of str2[i] hash2[str2.charAt(i)]++; } // Sort hash1[] array Arrays.sort(hash1); // Sort hash2[] array Arrays.sort(hash2); // Traverse hash1[] and hash2[] for (int i = 0; i < 256; i++) { // If hash1[i] not // equal to hash2[i] if (hash1[i] != hash2[i]) { return false; } } return true;}// Driver Codepublic static void main(String[] args){ String str1 = "xyyzzlll"; String str2 = "yllzzxxx"; if (checkStr1CanConStr2(str1, str2)) { System.out.print("True"); } else { System.out.print("False"); }}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachdef checkStr1CanConStr2(str1, str2): # Stores length of str1 N = len(str1) # Stores length of str2 M = len(str2) # Stores distinct characters # of str1 st1 = set([]) # Stores distinct characters # of str2 st2 = set([]) # Stores frequency of # each character of str1 hash1 = [0] * 256 # Traverse the string str1 for i in range(N): # Update frequency # of str1[i] hash1[ord(str1[i])] += 1 # Traverse the string str1 for i in range(N): # Insert str1[i] # into st1 st1.add(str1[i]) # Traverse the string str2 for i in range(M): # Insert str1[i] # into st1 st2.add(str2[i]) # If distinct characters in # str1 and str2 are not same if (st1 != st2): return False # Stores frequency of # each character of str2 hash2 = [0] * 256 # Traverse the string str2 for i in range(M): # Update frequency # of str2[i] hash2[ord(str2[i])] += 1 # Sort hash1[] array hash1.sort() # Sort hash2[] array hash2.sort() # Traverse hash1[] and hash2[] for i in range(256): # If hash1[i] not # equal to hash2[i] if (hash1[i] != hash2[i]): return False return True# Driver Codeif __name__ == "__main__": str1 = "xyyzzlll" str2 = "yllzzxxx" if (checkStr1CanConStr2(str1, str2)): print("True") else: print("False")# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{static bool checkStr1CanConStr2(String str1, String str2){ // Stores length of str1 int N = str1.Length; // Stores length of str2 int M = str2.Length; // Stores distinct characters // of str1 HashSet<int> st1 = new HashSet<int>(); // Stores distinct characters // of str2 HashSet<int> st2 = new HashSet<int>(); // Stores frequency of // each character of str1 int []hash1 = new int[256]; // Traverse the String str1 for (int i = 0; i < N; i++) { // Update frequency // of str1[i] hash1[str1[i]]++; } // Traverse the String str1 for (int i = 0; i < N; i++) { // Insert str1[i] // into st1 st1.Add(str1[i]); } // Traverse the String str2 for (int i = 0; i < M; i++) { // Insert str1[i] // into st1 st2.Add(str2[i]); } // If distinct characters in // str1 and str2 are not same if (st1.Equals(st2)) { return false; } // Stores frequency of // each character of str2 int []hash2 = new int[256]; // Traverse the String str2 for (int i = 0; i < M; i++) { // Update frequency // of str2[i] hash2[str2[i]]++; } // Sort hash1[] array Array.Sort(hash1); // Sort hash2[] array Array.Sort(hash2); // Traverse hash1[] and hash2[] for (int i = 0; i < 256; i++) { // If hash1[i] not // equal to hash2[i] if (hash1[i] != hash2[i]) { return false; } } return true;}// Driver Codepublic static void Main(String[] args){ String str1 = "xyyzzlll"; String str2 = "yllzzxxx"; if (checkStr1CanConStr2(str1, str2)) { Console.Write("True"); } else { Console.Write("False"); }}} // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approachfunction checkStr1CanConStr2(str1, str2){ // Stores length of str1 var N = str1.length; // Stores length of str2 var M = str2.length; // Stores distinct characters // of str1 var st1 = new Set(); // Stores distinct characters // of str2 var st2 = new Set(); // Stores frequency of // each character of str1 var hash1 = Array(256).fill(0); // Traverse the string str1 for (var i = 0; i < N; i++) { // Update frequency // of str1[i] hash1[str1[i].charCodeAt(0)]++; } // Traverse the string str1 for (var i = 0; i < N; i++) { // Insert str1[i] // into st1 st1.add(str1[i]); } // Traverse the string str2 for (var i = 0; i < M; i++) { // Insert str1[i] // into st1 st2.add(str2[i]); } // If distinct characters in // str1 and str2 are not same if (st1.size != st2.size) { return false; } // Stores frequency of // each character of str2 var hash2 = Array(256).fill(0); // Traverse the string str2 for (var i = 0; i < M; i++) { // Update frequency // of str2[i] hash2[str2[i].charCodeAt(0)]++; } // Sort hash1[] array hash1.sort((a,b)=>a-b); hash2.sort((a,b)=>a-b); // Traverse hash1[] and hash2[] for (var i = 0; i < 256; i++) { // If hash1[i] not // equal to hash2[i] if (hash1[i] != hash2[i]) { return false; } } return true;}// Driver Codevar str1 = "xyyzzlll";var str2 = "yllzzxxx";if (checkStr1CanConStr2(str1, str2)) { document.write( "True");}else { document.write( "False");}</script> |
Output:
True
Time Complexity: O(N + M + 256)
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!
