Given two strings str1 and str2, and a third-string shuffle, determine if shuffle is a valid shuffle of str1 and str2, where a valid shuffle contains all characters from str1 and str2 occurring the same number of times, regardless of order. Print “YES” if valid, and “NO” otherwise.
Examples:
Input: str1 = BA, str2 = XY, shuffle = XYAB
Output: YESInput: str1 = BA, str2 = XY, shuffle = XUMB
Output: NOInput: str1 = ABC, str2 = ZYS, shuffle = YBAZSC
Output:YES
Approach: To solve the problem follow the below idea:
The simplest approach that comes to mind is when we observe the given inputs carefully, we see that we only need to check if the frequency of each character in the string shuffle is exactly as it is in both the str1 and str2 and also the length should be of the length of str1 + length of str2. So, we can use a hashmap here.
Follow the steps to solve the problem:
- Create a hashmap
- Store the count of each character in both the given strings inside the hashmap
- Now, traverse on the string ‘shuffle’. And for every character encountered in string shuffle, look for it inside the hashmap.
- If the character is found then keep traversing till we reach the end of the substring and do the same for each character and decrease the frequency for each character that we come across.
- If any character isn’t found in the hashmap, then return false.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;bool validShuffle(string str1, string str2, string shuffle){ // n1 = size of str1, n2 = size of str2 int n1 = str1.size(); int n2 = str2.size(); // n = size of string shuffle int n = shuffle.size(); // Its obvious if the no. of char in // shuffle are more or less than the // length of str1 and str2 then it // won't be a valid shuffle if (n != n1 + n2) return false; // We use an unordered map to keep // track of frequency of // each character. unordered_map<int, int> freq; // Count frequency of each char // in str1 for (int i = 0; i < n1; i++) freq[str1[i]]++; // Count frequency of each char // in str2 for (int i = 0; i < n2; i++) freq[str2[i]]++; // If any of the char is not found in // the map, then its not a // valid shuffle. for (int i = 0; i < n; i++) { if (freq.find(shuffle[i]) != freq.end()) freq[shuffle[i]]--; else return false; } return true;}// Drivers codeint main(){ string str1 = "BA", str2 = "XY", shuffle = "ABYX"; (validShuffle(str1, str2, shuffle) == true) ? printf("YES") : printf("NO"); cout << endl; return 0;} |
Java
import java.util.HashMap;// Nikunj Sonigarapublic class GFG { static boolean validShuffle(String str1, String str2, String shuffle) { int n1 = str1.length(); int n2 = str2.length(); int n = shuffle.length(); if (n != n1 + n2) { return false; } HashMap<Character, Integer> freq = new HashMap<>(); for (int i = 0; i < n1; i++) { freq.put(str1.charAt(i), freq.getOrDefault(str1.charAt(i), 0) + 1); } for (int i = 0; i < n2; i++) { freq.put(str2.charAt(i), freq.getOrDefault(str2.charAt(i), 0) + 1); } for (int i = 0; i < n; i++) { if (freq.containsKey(shuffle.charAt(i))) { freq.put(shuffle.charAt(i), freq.get(shuffle.charAt(i)) - 1); } else { return false; } } return true; } public static void main(String[] args) { String str1 = "BA"; String str2 = "XY"; String shuffle = "ABYX"; if (validShuffle(str1, str2, shuffle)) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python3
def validShuffle(str1, str2, shuffle): n1 = len(str1) n2 = len(str2) n = len(shuffle) if n != n1 + n2: return False freq = {} for i in range(n1): if str1[i] in freq: freq[str1[i]] += 1 else: freq[str1[i]] = 1 for i in range(n2): if str2[i] in freq: freq[str2[i]] += 1 else: freq[str2[i]] = 1 for i in range(n): if shuffle[i] in freq: freq[shuffle[i]] -= 1 else: return False return Truestr1 = "BA"str2 = "XY"shuffle = "ABYX"if validShuffle(str1, str2, shuffle): print("YES")else: print("NO") |
C#
using System;using System.Collections.Generic;class Program{ static bool ValidShuffle(string str1, string str2, string shuffle) { // n1 = size of str1, n2 = size of str2 int n1 = str1.Length; int n2 = str2.Length; // n = size of string shuffle int n = shuffle.Length; // Its obvious if the no. of char in // shuffle are more or less than the // length of str1 and str2 then it // won't be a valid shuffle if (n != n1 + n2) { return false; } // We use an unordered map to keep // track of frequency of // each character. Dictionary<char, int> freq = new Dictionary<char, int>(); // Count frequency of each char // in str1 for (int i = 0; i < n1; i++) { if (freq.ContainsKey(str1[i])) { freq[str1[i]] += 1; } else { freq[str1[i]] = 1; } } // Count frequency of each char // in str2 for (int i = 0; i < n2; i++) { if (freq.ContainsKey(str2[i])) { freq[str2[i]] += 1; } else { freq[str2[i]] = 1; } } // If any of the char is not found in // the map, then its not a // valid shuffle. for (int i = 0; i < n; i++) { if (freq.ContainsKey(shuffle[i])) { freq[shuffle[i]] -= 1; } else { return false; } } return true; } // Drivers code static void Main(string[] args) { string str1 = "BA"; string str2 = "XY"; string shuffle = "ABYX"; if (ValidShuffle(str1, str2, shuffle)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
function validShuffle(str1, str2, shuffle) { const n1 = str1.length; const n2 = str2.length; const n = shuffle.length; if (n !== n1 + n2) return false; const freq = new Map(); for (let i = 0; i < n1; i++) freq.set(str1[i], (freq.get(str1[i]) || 0) + 1); for (let i = 0; i < n2; i++) freq.set(str2[i], (freq.get(str2[i]) || 0) + 1); for (let i = 0; i < n; i++) { if (freq.has(shuffle[i])) freq.set(shuffle[i], freq.get(shuffle[i]) - 1); else return false; } return true;}const str1 = "BA";const str2 = "XY";const shuffle = "ABYX";console.log(validShuffle(str1, str2, shuffle) ? "YES" : "NO"); |
Output
YES
Time Complexity: O(n) //In the above-given approach, there is one loop for iterating over string which takes O(N) time in worst case. Therefore, the time complexity for this approach will be O(N).
Auxiliary Space: O(n) // an unordered map is used and in the worst case all elements will be stored inside it the hence algorithm takes up linear 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!