Given an array of strings arr[][] of size N and a string S, the task is to find the number of strings from the array having all its characters appearing in the string S.
Examples:
Input: arr[][] = {“ab”, “aab”, “abaaaa”, “bbd”}, S = “ab”
Output: 3
Explanation: String “ab” have all the characters occurring in string S.
String “aab” have all the characters occurring in string S.
String “abaaaa” have all the characters occurring in string S.Input:arr[] = {“neveropen”, “for”, “neveropen”}, S = “ds”
Output: 0
Approach: The idea is to use Hashing to solve the problem. Follow the steps below to solve the problem:
- Initialize an unordered set of characters, say valid, and a counter variable, say cnt
- Insert all the characters of the string S into the set valid.
- Traverse the array arr[] and perform the following steps:
- Iterate over the characters of the string arr[i] and check if all the characters of string arr[i] occurs in string S or not with the help of the set valid.
- If found to be true, then increment cnt.
- Finally, print the result obtained cnt
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// strings from an array having all// characters appearing in the string Sint countStrings(string S, vector<string>& list){ // Initialize a set to store all // distinct characters of string S unordered_set<char> valid; // Traverse over string S for (auto x : S) { // Insert characters // into the Set valid.insert(x); } // Stores the required count int cnt = 0; // Traverse the array for (int i = 0; i < list.size(); i++) { int j = 0; // Traverse over string arr[i] for (j = 0; j < list[i].size(); j++) { // Check if character in arr[i][j] // is present in the string S or not if (valid.count(list[i][j])) continue; else break; } // Increment the count if all the characters // of arr[i] are present in the string S if (j == list[i].size()) cnt++; } // Finally, print the count return cnt;}// Driver codeint main(){ vector<string> arr = { "ab", "aab", "abaaaa", "bbd" }; string S = "ab"; cout << countStrings(S, arr) << endl;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to count the number of// Strings from an array having all// characters appearing in the String Sstatic int countStrings(String S, String []list){ // Initialize a set to store all // distinct characters of String S HashSet<Character> valid = new HashSet<Character>(); // Traverse over String S for (char x : S.toCharArray()) { // Insert characters // into the Set valid.add(x); } // Stores the required count int cnt = 0; // Traverse the array for (int i = 0; i < list.length; i++) { int j = 0; // Traverse over String arr[i] for (j = 0; j < list[i].length(); j++) { // Check if character in arr[i][j] // is present in the String S or not if (valid.contains(list[i].charAt(j))) continue; else break; } // Increment the count if all the characters // of arr[i] are present in the String S if (j == list[i].length()) cnt++; } // Finally, print the count return cnt;} // Driver codepublic static void main(String[] args){ String []arr = { "ab", "aab", "abaaaa", "bbd" }; String S = "ab"; System.out.print(countStrings(S, arr) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Function to count the number of# strings from an array having all# characters appearing in the string Sdef countStrings(S, list): # Initialize a set to store all # distinct characters of S valid = {} # Traverse over S for x in S: # Insert characters # into the Set valid[x] = 1 # Stores the required count cnt = 0 # Traverse the array for i in range(len(list)): j = 0 # Traverse over arr[i] while j < len(list[i]): # Check if character in arr[i][j] # is present in the S or not if (list[i][j] in valid): j += 1 continue else: break j += 1 # Increment the count if all the characters # of arr[i] are present in the S if (j == len(list[i])): cnt += 1 # Finally, print the count return cnt# Driver codeif __name__ == '__main__': arr = ["ab", "aab", "abaaaa", "bbd"] S,l = "ab",[] print(countStrings(S, arr))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the number of// Strings from an array having all// characters appearing in the String Sstatic int countStrings(String S, String []list){ // Initialize a set to store all // distinct characters of String S HashSet<char> valid = new HashSet<char>(); // Traverse over String S foreach (char x in S.ToCharArray()) { // Insert characters // into the Set valid.Add(x); } // Stores the required count int cnt = 0; // Traverse the array for (int i = 0; i < list.Length; i++) { int j = 0; // Traverse over String arr[i] for (j = 0; j < list[i].Length; j++) { // Check if character in arr[i,j] // is present in the String S or not if (valid.Contains(list[i][j])) continue; else break; } // Increment the count if all the characters // of arr[i] are present in the String S if (j == list[i].Length) cnt++; } // Finally, print the count return cnt;} // Driver codepublic static void Main(String[] args){ String []arr = { "ab", "aab", "abaaaa", "bbd" }; String S = "ab"; Console.Write(countStrings(S, arr) +"\n");}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement// the above approach// Function to count the number of// strings from an array having all// characters appearing in the string Sfunction countStrings(S, list){ // Initialize a set to store all // distinct characters of string S let valid = new Set(); // Traverse over string S for(let x of S) { // Insert characters // into the Set valid.add(x); } // Stores the required count let cnt = 0; // Traverse the array for(let i = 0; i < list.length; i++) { let j = 0; // Traverse over string arr[i] for(j = 0; j < list[i].length; j++) { // Check if character in arr[i][j] // is present in the string S or not if (valid.has(list[i][j])) continue; else break; } // Increment the count if all the characters // of arr[i] are present in the string S if (j == list[i].length) cnt++; } // Finally, print the count return cnt;}// Driver codelet arr = [ "ab", "aab", "abaaaa", "bbd" ];let S = "ab";document.write(countStrings(S, arr) + "<br>");// This code contributed by _saurabh_jaiswal</script> |
Output:
3
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
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!
