Check if a string can be constructed from another string
Given two strings, check if the second string can be constructed from characters of the first string, where each character of the first string can be used only once in the second string.
For example,
Output: true
Input: first = ab, second = abb
Output: false
We can use the hashing technique to solve this problem. The idea is to find the frequency of each character in the first string and store it in a hash table. Now, for each character of the second string, decrease its count in the hash table. If at some point the count becomes negative, we can say that the second string cannot be constructed from the first string.
Following is the C, C++, Java, and Python implementation based on the idea:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <stdio.h> int check(char* first, char* second) { // create a frequency map from the characters of the first string int freq[128] = { 0 }; for (int i = 0; i < strlen(first); i++) { freq[first[i]]++; } // iterate over each character of the second string and decrement its count for (int i = 0; i < strlen(second); i++) { // if the count becomes negative, the second string cannot be constructed // from the first if (--freq[first[i]] < 0) { return 0; } } return 1; } int main(void) { char* first = "abc"; char* second = "ab"; if (check(first, second)) { printf("True"); } else { printf("False"); } return 0; } |
Output:
true
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <unordered_map> using namespace std; bool check(string first, string second) { // create a frequency map from the characters of the first string std::unordered_map<char, int> freq; for (const char &c: first) { freq[c]++; } // iterate over each character of the second string and decrement its count for (auto &c: second) { // if the count becomes negative, the second string cannot be constructed // from the first if (--freq[c] < 0) { return false; } } return true; } int main() { string first = "abc"; string second = "ab"; cout << std::boolalpha << check(first, second); return 0; } |
Output:
true
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.HashMap; import java.util.Map; class Main { public static boolean check(String first, String second) { // create a frequency map from the characters of the first string Map<Character, Integer> freq = new HashMap<>(); for (char c: first.toCharArray()) { freq.put(c, freq.getOrDefault(c, 0) + 1); } // iterate over each character of the second string for (char c: second.toCharArray()) { // decrement the character's count freq.put(c, freq.getOrDefault(c, 0) - 1); // if the count becomes negative, // the second string cannot be constructed from the first if (freq.get(c) < 0) { return false; } } return true; } public static void main(String[] args) { String first = "abc"; String second = "ab"; System.out.println(check(first, second)); } } |
Output:
true
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def check(first, second): # create a frequency map from the characters of the first string freq = {} for c in first: freq[c] = freq.get(c, 0) + 1 # iterate over each character of the second string for c in second: # decrement the character's count freq[c] = freq.get(c, 0) - 1 # if the count becomes negative, # the second string cannot be constructed from the first if freq.get(c) < 0: return False return True if __name__ == '__main__': first = 'abc' second = 'ab' print(check(first, second)) |
Output:
True
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the string.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)