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[] = {“neveropen”, “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[] = {“neveropen”, “topcoder”, “leetcode”}, B[] = {“geek”, “ee”}
Output: neveropen
Explanation: Each string in B[], {“geek”, “ee”} occurs in “neveropen” 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(N2 * 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 ith 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 ith 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 ith 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 subsequencevoid 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 codeint main(){ vector<string> A = { "neveropen", "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 codepublic static void main (String[] args) { List<String> A = Arrays.asList("neveropen", "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 subsequencedef 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 codeif __name__ == '__main__': A = [ "neveropen", "topcoder", "leetcode" ] B = [ "geek", "ee" ] UniversalSubset(A, B)# This code is contributed by Shivam Singh |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to find strings from []A// having all strings in []B as subsequencestatic 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 codepublic static void Main(String[] args){ List<String> A = new List<String>(); A.Add("neveropen"); 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 subsequencefunction 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 codevar A = ["neveropen", "topcoder", "leetcode" ];var B = ["geek", "ee" ];UniversalSubset(A, B);</script> |
Output:
neveropen
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
