Check whether second string can be formed from characters of first string
Given two strings str1 and str2, check if str2 can be formed from str1
Example :
Input : str1 = geekforBeginner, str2 = Beginner
Output : Yes
Here, string2 can be formed from string1.Input : str1 = geekforBeginner, str2 = and
Output : No
Here string2 cannot be formed from string1.Input : str1 = geekforBeginner, str2 = geeeek
Output : Yes
Here string2 can be formed from string1
as string1 contains ‘e’ comes 4 times in
string2 which is present in string1.
The idea is to count frequencies of characters of str1 in a count array. Then traverse str2 and decrease frequency of characters of str2 in the count array. If frequency of a characters becomes negative at any point, return false.
Below is the implementation of above approach :
C++
// CPP program to check whether second string // can be formed from first string #include <bits/stdc++.h> using namespace std; const int MAX = 256; bool canMakeStr2(string str1, string str2) { // Create a count array and count frequencies // characters in str1. int count[MAX] = {0}; for ( int i = 0; i < str1.length(); i++) count[str1[i]]++; // Now traverse through str2 to check // if every character has enough counts for ( int i = 0; i < str2.length(); i++) { if (count[str2[i]] == 0) return false ; count[str2[i]]--; } return true ; } // Driver Code int main() { string str1 = "geekforBeginner" ; string str2 = "for" ; if (canMakeStr2(str1, str2)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to check whether second string // can be formed from first string class GFG { static int MAX = 256 ; static boolean canMakeStr2(String str1, String str2) { // Create a count array and count frequencies // characters in str1. int [] count = new int [MAX]; char []str3 = str1.toCharArray(); for ( int i = 0 ; i < str3.length; i++) count[str3[i]]++; // Now traverse through str2 to check // if every character has enough counts char []str4 = str2.toCharArray(); for ( int i = 0 ; i < str4.length; i++) { if (count[str4[i]] == 0 ) return false ; count[str4[i]]--; } return true ; } // Driver Code static public void main(String []args) { String str1 = "geekforBeginner" ; String str2 = "for" ; if (canMakeStr2(str1, str2)) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
# Python program to check whether second string # can be formed from first string def canMakeStr2(s1, s2): # Create a count array and count # frequencies characters in s1 count = {s1[i] : 0 for i in range ( len (s1))} for i in range ( len (s1)): count[s1[i]] + = 1 # Now traverse through str2 to check # if every character has enough counts for i in range ( len (s2)): if (count.get(s2[i]) = = None or count[s2[i]] = = 0 ): return False count[s2[i]] - = 1 return True # Driver Code s1 = "geekforBeginner" s2 = "for" if canMakeStr2(s1, s2): print ( "Yes" ) else : print ( "No" ) |
C#
// C# program to check whether second string // can be formed from first string using System; class GFG { static int MAX = 256; static bool canMakeStr2( string str1, string str2) { // Create a count array and count frequencies // characters in str1. int [] count = new int [MAX]; for ( int i = 0; i < str1.Length; i++) count[str1[i]]++; // Now traverse through str2 to check // if every character has enough counts for ( int i = 0; i < str2.Length; i++) { if (count[str2[i]] == 0) return false ; count[str2[i]]--; } return true ; } // Driver Code static public void Main() { string str1 = "geekforBeginner" ; string str2 = "for" ; if (canMakeStr2(str1, str2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to check whether // second string can be formed // from first string $MAX = 256; function canMakeStr2( $str1 , $str2 ) { // Create a count array and // count frequencies characters // in str1. $count = (0); for ( $i = 0; $i < strlen ( $str1 ); $i ++) // Now traverse through str2 // to check if every character // has enough counts for ( $i = 0; $i < strlen ( $str2 ); $i ++) { if ( $count [ $str2 [ $i ]] == 0) return -1; } return true; } // Driver Code $str1 = "geekforBeginner" ; $str2 = "for" ; if (canMakeStr2( $str1 , $str2 )) echo "Yes" ; else echo "No" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program to check whether second string // can be formed from first string function canMakeStr2(str1, str2) { // Create a count array and count frequencies // characters in str1. let count = {}; // count.fill(0); for (let i = 0; i < str1.length; i++) { if (str1[i] in count) count[str1[i]]++; else count[str1[i]] = 1 } // Now traverse through str2 to check // if every character has enough counts for (let i = 0; i < str2.length; i++) { if (count[str2[i]] == 0 || !(str2[i] in count)) return false ; count[str2[i]]--; } return true ; } let str1 = "geekforBeginner" ; let str2 = "gggeek" ; if (canMakeStr2(str1, str2)) document.write( "Yes" ); else document.write( "No" ); </script> |
Yes
Time Complexity: O(n+m), where n and m are the length of the given strings.
Auxiliary Space: O(256), which is constant.