Given two strings str1 of size N and str2 of size M.The task is to find if it is possible to compose str2 by using only the characters of str1 such that every character of str1 can be used any number of time.
Note: Lower case letters and upper case letters should be considered different.
Examples:
Input: str1 = “The quick brown fox jumps”, str2 = “the fox was quicker than the dog”
Output: No
Explanation:
In str2, there is d character, which is not present in str1. So, it is impossible to make the string str2 from str1
Input: str1 = “we all love neveropen”, str2 = “we all love neveropen”
Output: Yes
Naive Approach: The simplest approach is to search for every character of str2 in str1. If all the characters are found then print “Yes”. Otherwise, print “No”.
Implementation of the above approach
C++
#include <iostream>#include <unordered_map>using namespace std;string can_compose_str(string str1, string str2) { unordered_map<char, int> freq_map; for (char ch : str1) { freq_map[ch]++; } for (char ch : str2) { if (freq_map.find(ch) == freq_map.end() || freq_map[ch] < 1) { return "No"; } freq_map[ch]--; } return "Yes";}int main() { string str1 = "abcdef"; string str2 = "abcde"; cout << can_compose_str(str1, str2) << endl; // Output: Yes return 0;} |
Java
import java.util.HashMap;import java.util.Map;public class Main { public static String canComposeStr(String str1, String str2) { Map<Character, Integer> freqMap = new HashMap<>(); for (char ch : str1.toCharArray()) { freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1); } for (char ch : str2.toCharArray()) { if (!freqMap.containsKey(ch) || freqMap.get(ch) < 1) { return "No"; } freqMap.put(ch, freqMap.get(ch) - 1); } return "Yes"; } public static void main(String[] args) { String str1 = "abcdef"; String str2 = "abcde"; System.out.println(canComposeStr(str1, str2)); // Output: Yes }} |
Python
def can_compose_str(str1, str2): freq_map = {} for ch in str1: freq_map[ch] = freq_map.get(ch, 0) + 1 for ch in str2: if ch not in freq_map or freq_map[ch] < 1: return "No" freq_map[ch] -= 1 return "Yes"str1 = "abcdef"str2 = "abcde"print(can_compose_str(str1, str2)) # Output: Yes |
C#
using System;using System.Collections.Generic;public class Program { public static string CanComposeStr(string str1, string str2) { Dictionary<char, int> freqMap = new Dictionary<char, int>(); foreach (char ch in str1) { if (freqMap.ContainsKey(ch)) { freqMap[ch]++; } else { freqMap[ch] = 1; } } foreach (char ch in str2) { if (!freqMap.ContainsKey(ch) || freqMap[ch] < 1) { return "No"; } freqMap[ch]--; } return "Yes"; } public static void Main() { string str1 = "abcdef"; string str2 = "abcde"; Console.WriteLine(CanComposeStr(str1, str2)); // Output: Yes }} |
Javascript
function canComposeStr(str1, str2) { let freqMap = new Map(); for (let ch of str1) { freqMap.set(ch, freqMap.get(ch) + 1 || 1); } for (let ch of str2) { if (!freqMap.has(ch) || freqMap.get(ch) < 1) { return "No"; } freqMap.set(ch, freqMap.get(ch) - 1); } return "Yes";}let str1 = "abcdef";let str2 = "abcde";console.log(canComposeStr(str1, str2)); // Output: Yes |
Output
Yes
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Efficient Approach: The idea is to mark the presence of all characters of str1 in a count[] array. Then traverse str2 and check if the characters of str2 is present in str1 or not.
- Make an array count[] of size 256 (number of total ASCII characters ) and set it to zero.
- Then iterate over str1 and make count[str[i]] = 1 to mark the occurrence of every character.
- Iterate over str2 and check if that character is present in str1 or not using count[] array.
Below is the implementation of the above approach:
CPP
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if// str2 can be made by characters// of str1 or notvoid isPossible(string str1, string str2){ // To store the // occurrence of every // character int arr[256] = { 0 }; // Length of the two // strings int l1 = str1.size(); int l2 = str2.size(); int i, j; // Assume that it is // possible to compose the // string str2 from str1 bool possible = true; // Iterate over str1 for (i = 0; i < l1; i++) { // Store the presence of every // character arr[str1[i]] = 1; } // Iterate over str2 for (i = 0; i < l2; i++) { // Ignore the spaces if (str2[i] != ' ') { // Check for the presence // of character in str1 if (arr[str2[i]] == 1) continue; else { possible = false; break; } } } // If it is possible to make // str2 from str1 if (possible) { cout << "Yes" << endl; } else { cout << "No" << endl; }}// Driver Codeint main(){ // Given strings string str1 = "we all love neveropen"; string str2 = "we all love neveropen"; // Function Call isPossible(str1, str2); return 0;} |
Java
// Java implementation of// the above approachimport java.util.Arrays;class GFG { // Function to check if // str2 can be made by characters // of str1 or not public static void isPossible(String str1, String str2) { // To store the // occurrence of every // character int arr[] = new int[256]; Arrays.fill(arr, 0); // Length of the two // strings int l1 = str1.length(); int l2 = str2.length(); int i, j; // Assume that it is // possible to compose the // string str2 from str1 boolean possible = true; // Iterate over str1 for (i = 0; i < l1; i++) { // Store the presence of every // character arr[str1.charAt(i)] = 1; } // Iterate over str2 for (i = 0; i < l2; i++) { // Ignore the spaces if (str2.charAt(i) != ' ') { // Check for the presence // of character in str1 if (arr[str2.charAt(i)] == 1) continue; else { possible = false; break; } } } // If it is possible to make // str2 from str1 if (possible) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver Code public static void main(String args[]) { // Given strings String str1 = "we all love neveropen"; String str2 = "we all love neveropen"; // Function Call isPossible(str1, str2); }}// This code is contributed by saurabh_jaiswal. |
C#
// C# implementation of// the above approachusing System;using System.Collections.Generic;class GFG{// Function to check if// str2 can be made by characters// of str1 or notstatic void isPossible(string str1, string str2){ // To store the // occurrence of every // character int []arr = new int[256]; Array.Clear(arr,0,256); // Length of the two // strings int l1 = str1.Length; int l2 = str2.Length; int i; // Assume that it is // possible to compose the // string str2 from str1 bool possible = true; // Iterate over str1 for (i = 0; i < l1; i++) { // Store the presence of every // character arr[str1[i]] = 1; } // Iterate over str2 for (i = 0; i < l2; i++) { // Ignore the spaces if (str2[i] != ' ') { // Check for the presence // of character in str1 if (arr[str2[i]] == 1) continue; else { possible = false; break; } } } // If it is possible to make // str2 from str1 if (possible) { Console.Write("Yes"); } else { Console.Write("No"); }}// Driver Codepublic static void Main(){ // Given strings string str1 = "we all love neveropen"; string str2 = "we all love neveropen"; // Function Call isPossible(str1, str2);}}// This code is contributed by ipg2016107. |
Python3
# Python3 implementation of# the above approach# Function to check if# str2 can be made by characters# of str1 or notdef isPossible(str1, str2): # To store the # occurrence of every # character arr = {} # Length of the two # strings l1 = len(str1) l2 = len(str2) # Assume that it is # possible to compose the # string str2 from str1 possible = True # Iterate over str1 for i in range(l1): # Store the presence or every element arr[str1[i]] = 1 # Iterate over str2 for i in range(l2): # Ignore the spaces if str2[i] != ' ': # Check for the presence # of character in str1 if arr[str2[i]] == 1: continue else: possible = False break # If it is possible to make # str2 from str1 if possible: print("Yes") else: print("No")# Driver codestr1 = "we all love neveropen"str2 = "we all love neveropen"# Function call.isPossible(str1, str2)# This code is contributed by Parth Manchanda |
Javascript
<script>// JavaScript implementation of// the above approach// Function to check if// str2 can be made by characters// of str1 or notfunction isPossible(str1, str2) { // To store the // occurrence of every // character let arr = new Array(256).fill(0); // Length of the two // strings let l1 = str1.length; let l2 = str2.length; let i, j; // Assume that it is // possible to compose the // string str2 from str1 let possible = true; // Iterate over str1 for (i = 0; i < l1; i++) { // Store the presence of every // character arr[str1[i]] = 1; } // Iterate over str2 for (i = 0; i < l2; i++) { // Ignore the spaces if (str2[i] != " ") { // Check for the presence // of character in str1 if (arr[str2[i]] == 1) continue; else { possible = false; break; } } } // If it is possible to make // str2 from str1 if (possible) { document.write("Yes<br>"); } else { document.write("No<br>"); }}// Driver Code// Given stringslet str1 = "we all love neveropen";let str2 = "we all love neveropen";// Function CallisPossible(str1, str2);</script> |
Output
Yes
Time Complexity: O(N+M)
Auxiliary Space: O(1)
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!