Print all Strings from array A[] having all strings from array B[] as subsequence

0 0 8 minutes read

Given two arrays A[] and B[] consisting of strings, the task is to print the strings from array A[] having all strings in B[] as a subsequence.
Examples:

Input: A[] = {“zambiatek”, “mapple”, “twitter”, “table”, “Linkedin”}, B[] = {“e”, “l”}
Output: mapple table linkedin
Explanation: Both the strings “e” and “l” are subsets in “mapple”, “table”, “linkedin”.
Input: A[] = {“zambiatek”, “topcoder”, “leetcode”}, B[] = {“geek”, “ee”}
Output: zambiatek
Explanation: Each string in B[], {“geek”, “ee”} occurs in “zambiatek” only.

Naive Approach:
The simplest approach to solve the problem is to traverse array A[] and for every string, check if all the strings in array B[] are present in it as a subsequence or not.
Time complexity: O(N² * L), where length denotes the maximum length of a string in array A[]
Auxiliary Space: O(1)
Efficient Approach:
To optimize the above approach, follow the steps below:

Initialize a matrix A_fre[][], in which A_fre[i] stores the frequency of each character in i^th string.
Initialize B_fre[] to store frequency of all characters in the strings in array B[].
Traverse over array A[] and for every string, check if a character has more frequency in the strings of array B[] than in i^th string in A[], i.e.

if A_fre[i][j] < B_fre[j], where
A_fre[i][j]: Frequency of the character with ASCII value (‘a’ + j) in i^th string in A[].
B_fre[j]: Frequency of the character with ASCII value (‘a’ + j) in the strings of B[].

then that string has at least one string in B[] which is not its subsequence.
If the above condition is not satisfied for all characters for any string in A[], print that string as an answer.
After checking all strings in A[], if no string is found to be having all strings in B[] as its proper subset, print -1.

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 find strings from A[]
// having all strings in B[] as subsequence
void UniversalSubset(vector<string> A,
                     vector<string> B)
{
    // Calculate respective sizes
    int n1 = A.size();
    int n2 = B.size();
 
    // Stores the answer
    vector<string> res;
 
    // Stores the frequency of each
    // character in strings of A[]
    int A_fre[n1][26];
 
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < 26; j++)
            A_fre[i][j] = 0;
    }
 
    // Compute the frequencies
    // of characters of all strings
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < A[i].size();
             j++) {
            A_fre[i][A[i][j] - 'a']++;
        }
    }
 
    // Stores the frequency of each
    // character in strings of B[]
    // each character of a string in B[]
    int B_fre[26] = { 0 };
 
    for (int i = 0; i < n2; i++) {
        int arr[26] = { 0 };
        for (int j = 0; j < B[i].size();
             j++) {
 
            arr[B[i][j] - 'a']++;
            B_fre[B[i][j] - 'a']
                = max(B_fre[B[i][j] - 'a'],
                      arr[B[i][j] - 'a']);
        }
    }
 
    for (int i = 0; i < n1; i++) {
        int flag = 0;
        for (int j = 0; j < 26; j++) {
 
            // If the frequency of a character
            // in B[] exceeds that in A[]
            if (A_fre[i][j] < B_fre[j]) {
 
                // A string exists in B[] which
                // is not a proper subset of A[i]
                flag = 1;
                break;
            }
        }
 
        // If all strings in B[] are
        // proper subset of A[]
        if (flag == 0)
            // Push the string in
            // resultant vector
            res.push_back(A[i]);
    }
 
    // If any string is found
    if (res.size()) {
 
        // Print those strings
        for (int i = 0; i < res.size();
             i++) {
            for (int j = 0; j < res[i].size();
                 j++)
                cout << res[i][j];
        }
 
        cout << " ";
    }
 
    // Otherwise
    else
        cout << "-1";
}
 
// Driver code
int main()
{
    vector<string> A = { "zambiatek",
                         "topcoder",
                         "leetcode" };
    vector<string> B = { "geek", "ee" };
 
    UniversalSubset(A, B);
 
    return 0;
}

Java

// Java program to implement 
// the above approach 
import java.util.*;
 
class GFG {
     
// Function to find strings from A[] 
// having all strings in B[] as subsequence 
static void UniversalSubset(List<String> A, 
                            List<String> B) 
{ 
     
    // Calculate respective sizes 
    int n1 = A.size(); 
    int n2 = B.size(); 
 
    // Stores the answer 
    List<String> res = new ArrayList<>(); 
 
    // Stores the frequency of each 
    // character in strings of A[] 
    int[][] A_fre = new int[n1][26]; 
 
    for(int i = 0; i < n1; i++)
    { 
        for(int j = 0; j < 26; j++) 
            A_fre[i][j] = 0; 
    } 
 
    // Compute the frequencies 
    // of characters of all strings 
    for(int i = 0; i < n1; i++)
    { 
        for(int j = 0; j < A.get(i).length(); j++) 
        { 
            A_fre[i][A.get(i).charAt(j) - 'a']++; 
        } 
    } 
 
    // Stores the frequency of each 
    // character in strings of B[] 
    // each character of a string in B[] 
    int[] B_fre = new int[26]; 
 
    for(int i = 0; i < n2; i++)
    { 
        int[] arr = new int[26] ; 
        for(int j = 0; j < B.get(i).length(); j++)
        { 
            arr[B.get(i).charAt(j) - 'a']++; 
            B_fre[B.get(i).charAt(j) - 'a'] = Math.max(
            B_fre[B.get(i).charAt(j) - 'a'], 
              arr[B.get(i).charAt(j) - 'a']); 
        } 
    } 
 
    for(int i = 0; i < n1; i++)
    { 
        int flag = 0; 
        for(int j = 0; j < 26; j++) 
        { 
 
            // If the frequency of a character 
            // in B[] exceeds that in A[] 
            if (A_fre[i][j] < B_fre[j])
            { 
                 
                // A string exists in B[] which 
                // is not a proper subset of A[i] 
                flag = 1; 
                break; 
            } 
        } 
 
        // If all strings in B[] are 
        // proper subset of A[] 
        if (flag == 0) 
         
            // Push the string in 
            // resultant vector 
            res.add(A.get(i)); 
    } 
 
    // If any string is found 
    if (res.size() != 0)
    { 
         
        // Print those strings 
        for(int i = 0; i < res.size(); i++) 
        { 
            for(int j = 0; 
                    j < res.get(i).length();
                    j++) 
            System.out.print(res.get(i).charAt(j)); 
        } 
        System.out.print(" "); 
    } 
 
    // Otherwise 
    else
    System.out.print("-1"); 
}
 
// Driver code
public static void main (String[] args) 
{
    List<String> A = Arrays.asList("zambiatek", 
                                   "topcoder", 
                                   "leetcode"); 
    List<String> B = Arrays.asList("geek", "ee"); 
     
    UniversalSubset(A, B); 
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to implement
# the above approach
 
# Function to find strings from A[]
# having all strings in B[] as subsequence
def UniversalSubset(A, B):
 
    # Calculate respective sizes
    n1 = len(A)
    n2 = len(B)
 
    # Stores the answer
    res = []
 
    # Stores the frequency of each
    # character in strings of A[]
    A_freq = [[0 for x in range(26)]
                 for y in range(n1)]
 
    # Compute the frequencies
    # of characters of all strings
    for i in range(n1):
        for j in range(len(A[i])):
            A_freq[i][ord(A[i][j]) - ord('a')] += 1
 
    # Stores the frequency of each
    # character in strings of B[]
    # each character of a string in B[]
    B_freq = [0] * 26
 
    for i in range(n2):
        arr = [0] * 26
         
        for j in range(len(B[i])):
            arr[ord(B[i][j]) - ord('a')] += 1
             
            B_freq[ord(B[i][j]) - ord('a')] = max(
            B_freq[ord(B[i][j]) - ord('a')],
               arr[ord(B[i][j]) - ord('a')])
 
    for i in range(n1):
        flag = 0
        for j in range(26):
 
            # If the frequency of a character
            # in B[] exceeds that in A[]
            if(A_freq[i][j] < B_freq[j]):
 
                # A string exists in B[] which
                # is not a proper subset of A[i]
                flag = 1
                break
 
        # If all strings in B[] are
        # proper subset of A[]
        if(flag == 0):
             
            # Push the string in
            # resultant vector
            res.append(A[i])
 
    # If any string is found
    if(len(res)):
 
        # Print those strings
        for i in range(len(res)):
            for j in range(len(res[i])):
                print(res[i][j], end = "")
 
    # Otherwise 
    else:
        print(-1, end = "")
 
# Driver code
if __name__ == '__main__':
 
    A = [ "zambiatek", "topcoder", 
          "leetcode" ]
    B = [ "geek", "ee" ]
 
    UniversalSubset(A, B)
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find strings from []A
// having all strings in []B as subsequence
static void UniversalSubset(List<String> A,
                            List<String> B)
{
     
    // Calculate respective sizes
    int n1 = A.Count;
    int n2 = B.Count;
 
    // Stores the answer
    List<String> res = new List<String>();
 
    // Stores the frequency of each
    // character in strings of []A
    int[,] A_fre = new int[n1, 26];
 
    for(int i = 0; i < n1; i++)
    {
        for(int j = 0; j < 26; j++)
            A_fre[i, j] = 0;
    }
 
    // Compute the frequencies
    // of characters of all strings
    for(int i = 0; i < n1; i++)
    {
        for(int j = 0; j < A[i].Length; j++)
        {
            A_fre[i, A[i][j] - 'a']++;
        }
    }
 
    // Stores the frequency of each
    // character in strings of []B
    // each character of a string in []B
    int[] B_fre = new int[26];
 
    for(int i = 0; i < n2; i++)
    {
        int[] arr = new int[26];
        for(int j = 0; j < B[i].Length; j++)
        {
            arr[B[i][j] - 'a']++;
            B_fre[B[i][j] - 'a'] = Math.Max(
                                   B_fre[B[i][j] - 'a'],
                                     arr[B[i][j] - 'a']);
        }
    }
 
    for(int i = 0; i < n1; i++)
    {
        int flag = 0;
        for(int j = 0; j < 26; j++) 
        {
             
            // If the frequency of a character
            // in []B exceeds that in []A
            if (A_fre[i, j] < B_fre[j])
            {
                 
                // A string exists in []B which
                // is not a proper subset of A[i]
                flag = 1;
                break;
            }
        }
 
        // If all strings in []B are
        // proper subset of []A
        if (flag == 0)
 
            // Push the string in
            // resultant vector
            res.Add(A[i]);
    }
 
    // If any string is found
    if (res.Count != 0)
    {
         
        // Print those strings
        for(int i = 0; i < res.Count; i++)
        {
            for(int j = 0; j < res[i].Length; j++)
                Console.Write(res[i][j]);
        }
        Console.Write(" ");
    }
 
    // Otherwise
    else
        Console.Write("-1");
}
 
// Driver code
public static void Main(String[] args)
{
    List<String> A = new List<String>();
    A.Add("zambiatek");
    A.Add("topcoder");
    A.Add("leetcode");
     
    List<String> B = new List<String>();
    B.Add("geek");
    B.Add("ee");
 
    UniversalSubset(A, B);
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
  
// Javascript Program to implement the
// above approach
 
// Function to find strings from A[]
// having all strings in B[] as subsequence
function UniversalSubset(A, B)
{
    // Calculate respective sizes
    var n1 = A.length;
    var n2 = B.length;
 
    // Stores the answer
    var res = [];
 
    // Stores the frequency of each
    // character in strings of A[]
    var A_fre = Array.from( Array(n1), ()=> Array(26));
 
    for (var i = 0; i < n1; i++) {
        for (var j = 0; j < 26; j++)
            A_fre[i][j] = 0;
    }
 
    // Compute the frequencies
    // of characters of all strings
    for (var i = 0; i < n1; i++) {
        for (var j = 0; j < A[i].length;
             j++) {
            A_fre[i][A[i].charCodeAt(j) - 'a'.charCodeAt(0)]++;
        }
    }
 
    // Stores the frequency of each
    // character in strings of B[]
    // each character of a string in B[]
    var B_fre = Array(26).fill(0);
 
    for (var i = 0; i < n2; i++) {
        var arr = Array(26).fill(0);
        for (var j = 0; j < B[i].length;
             j++) {
 
            arr[B[i].charCodeAt(j) - 'a'.charCodeAt(0)]++;
            B_fre[B[i].charCodeAt(j) - 'a'.charCodeAt(0)]
                = Math.max(B_fre[B[i].charCodeAt(j) - 'a'.charCodeAt(0)],
                      arr[B[i].charCodeAt(j)- 'a'.charCodeAt(0)]);
        }
    }
 
    for (var i = 0; i < n1; i++) {
        var flag = 0;
        for (var j = 0; j < 26; j++) {
 
            // If the frequency of a character
            // in B[] exceeds that in A[]
            if (A_fre[i][j] < B_fre[j]) {
 
                // A string exists in B[] which
                // is not a proper subset of A[i]
                flag = 1;
                break;
            }
        }
 
        // If all strings in B[] are
        // proper subset of A[]
        if (flag == 0)
            // Push the string in
            // resultant vector
            res.push(A[i]);
    }
 
    // If any string is found
    if (res.length>0) {
 
        // Print those strings
        for (var i = 0; i < res.length;
             i++) {
            for (var j = 0; j < res[i].length;
                 j++)
                document.write( res[i][j]);
        }
 
        document.write( " ");
    }
 
    // Otherwise
    else
        document.write( "-1");
}
 
// Driver code
var A = ["zambiatek",
                     "topcoder",
                     "leetcode" ];
var B = ["geek", "ee" ];
UniversalSubset(A, B);
 
 
</script>

Output:

zambiatek

Time Complexity: O(N * * L), where length denotes the maximum length of a string in array A[].
Auxiliary Space: O(N)

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!