Count strings from given array having all characters appearing in a given string

0 0 5 minutes read

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[] = {“zambiatek”, “for”, “zambiatek”}, 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 S
int 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 code
int main()
{
    vector<string> arr = { "ab", "aab",
                           "abaaaa", "bbd" };
    string S = "ab";
 
    cout << countStrings(S, arr) << endl;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG
{
 
// Function to count the number of
// Strings from an array having all
// characters appearing in the String S
static 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 code
public 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 S
def 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 code
if __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 approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to count the number of
// Strings from an array having all
// characters appearing in the String S
static 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 code
public 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 S
function 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 code
let arr = [ "ab", "aab",
            "abaaaa", "bbd" ];
let S = "ab";
 
document.write(countStrings(S, arr) + "<br>");
 
// This code contributed by _saurabh_jaiswal
 
</script>

Output:

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 zambiatek!