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 w3wiki”, str2 = “we all love Beginner”
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;
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));
}
}
|
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))
|
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));
}
}
|
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));
|
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
#include <bits/stdc++.h>
using namespace std;
void isPossible(string str1, string str2)
{
int arr[256] = { 0 };
int l1 = str1.size();
int l2 = str2.size();
int i, j;
bool possible = true ;
for (i = 0; i < l1; i++) {
arr[str1[i]] = 1;
}
for (i = 0; i < l2; i++) {
if (str2[i] != ' ' ) {
if (arr[str2[i]] == 1)
continue ;
else {
possible = false ;
break ;
}
}
}
if (possible) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
int main()
{
string str1 = "we all love w3wiki" ;
string str2 = "we all love Beginner" ;
isPossible(str1, str2);
return 0;
}
|
Java
import java.util.Arrays;
class GFG {
public static void isPossible(String str1, String str2) {
int arr[] = new int [ 256 ];
Arrays.fill(arr, 0 );
int l1 = str1.length();
int l2 = str2.length();
int i, j;
boolean possible = true ;
for (i = 0 ; i < l1; i++) {
arr[str1.charAt(i)] = 1 ;
}
for (i = 0 ; i < l2; i++) {
if (str2.charAt(i) != ' ' ) {
if (arr[str2.charAt(i)] == 1 )
continue ;
else {
possible = false ;
break ;
}
}
}
if (possible) {
System.out.println( "Yes" );
} else {
System.out.println( "No" );
}
}
public static void main(String args[])
{
String str1 = "we all love w3wiki" ;
String str2 = "we all love Beginner" ;
isPossible(str1, str2);
}
}
|
C#
using System;
using System.Collections.Generic;
class GFG{
static void isPossible( string str1, string str2)
{
int []arr = new int [256];
Array.Clear(arr,0,256);
int l1 = str1.Length;
int l2 = str2.Length;
int i;
bool possible = true ;
for (i = 0; i < l1; i++) {
arr[str1[i]] = 1;
}
for (i = 0; i < l2; i++) {
if (str2[i] != ' ' ) {
if (arr[str2[i]] == 1)
continue ;
else {
possible = false ;
break ;
}
}
}
if (possible) {
Console.Write( "Yes" );
}
else {
Console.Write( "No" );
}
}
public static void Main()
{
string str1 = "we all love w3wiki" ;
string str2 = "we all love Beginner" ;
isPossible(str1, str2);
}
}
|
Python3
def isPossible(str1, str2):
arr = {}
l1 = len (str1)
l2 = len (str2)
possible = True
for i in range (l1):
arr[str1[i]] = 1
for i in range (l2):
if str2[i] ! = ' ' :
if arr[str2[i]] = = 1 :
continue
else :
possible = False
break
if possible:
print ( "Yes" )
else :
print ( "No" )
str1 = "we all love w3wiki"
str2 = "we all love Beginner"
isPossible(str1, str2)
|
Javascript
<script>
function isPossible(str1, str2) {
let arr = new Array(256).fill(0);
let l1 = str1.length;
let l2 = str2.length;
let i, j;
let possible = true ;
for (i = 0; i < l1; i++) {
arr[str1[i]] = 1;
}
for (i = 0; i < l2; i++) {
if (str2[i] != " " ) {
if (arr[str2[i]] == 1) continue ;
else {
possible = false ;
break ;
}
}
}
if (possible) {
document.write( "Yes<br>" );
} else {
document.write( "No<br>" );
}
}
let str1 = "we all love w3wiki" ;
let str2 = "we all love Beginner" ;
isPossible(str1, str2);
</script>
|
Time Complexity: O(N+M)
Auxiliary Space: O(1)