Count of lists which are not a subset of any other given lists
Given N lists of strings, the task is to find the count of lists that are not a sublist of any other given lists.
Examples:
Input: [[“hey”, “hi”, “hello”], [“hey”, “bye”], [“hey”, “hi”]]
Output: 2
Explanation The third list is a subset of the first list, hence the first and the second list are the required lists.
Input: [[“w3wiki”, “Beginner”], [“Beginner”, “w3wiki”]]
Output: 0
Explanation: Both the lists comprise of same set of strings.
Approach
Follow the steps below to solve the problem:
- First of all, enumerate all the possible strings in all vectors, i.e. assign them an integer.
- Then, use a Bitset for all individual lists to store the strings present in them.
- Compare the bitsets. If one of the bitsets is a subset of another, ignore that list. Otherwise insert the index of that list in a set.
- Print all the indices in the set.
Below is the implementation of the above approach:
C++
// C++ program to find all lists // which are not a subset of any // other given lists #include <bits/stdc++.h> using namespace std; #define N 50005 // Function to print all lists which // are not a subset of any other lists void findNonSubsets(vector<vector<string> >& v, vector< int >& ans) { unordered_map<string, int > mp; int id = 1; // Enumerate all strings // present in all lists for ( int i = 0; i < v.size(); i++) { for ( int j = 0; j < v[i].size(); j++) { if (mp.count(v[i][j]) > 0) continue ; mp[v[i][j]] = id++; } } // Compute and store bitsets // of all strings in lists vector<bitset<N> > v1; for ( int i = 0; i < v.size(); i++) { bitset<N> b; for ( int j = 0; j < v[i].size(); j++) { b[mp[v[i][j]]] = 1; } v1.push_back(b); } for ( int i = 0; i < v.size(); i++) { bool flag = false ; for ( int j = 0; !flag and j < v.size(); j++) { if (i != j) { // If one of the bitsets is // a subset of another, the // logical AND is equal to the // subset(intersection operation) if ((v1[i] & v1[j]) == v1[i]) { flag = true ; } } } if (!flag) { ans.push_back(i); } } return ; } // Driver Program signed main() { vector<vector<string> > v = { { "hey" , "hello" , "hi" }, { "hey" , "bye" }, { "hey" , "hi" } }; vector< int > ans; findNonSubsets(v, ans); if (ans.size() == 0) { cout << -1 << endl; return 0; } for ( int i = 0; i < ans.size(); i++) { cout << ans[i] << " " ; } return 0; } |
Java
import java.util.*; public class Main { // Java implementation to find all lists which are not a subset of any other given lists public static void findNonSubsets(String[][] v, List<Integer> ans) { Map<String, Integer> mp = new HashMap<>(); int id = 1 ; // Enumerate all strings present in all lists for ( int i = 0 ; i < v.length; i++) { for ( int j = 0 ; j < v[i].length; j++) { if (mp.containsKey(v[i][j])) continue ; mp.put(v[i][j], id++); } } // Compute and store bitsets of all strings in lists List< int []> v1 = new ArrayList<>(); for ( int i = 0 ; i < v.length; i++) { int [] b = new int [id]; for ( int j = 0 ; j < v[i].length; j++) { b[mp.get(v[i][j])] = 1 ; } v1.add(b); } for ( int i = 0 ; i < v.length; i++) { boolean flag = false ; for ( int j = 0 ; !flag && j < v.length; j++) { if (i != j) { // If one of the bitsets is a subset of another, the logical AND is equal to the subset (intersection operation) int res = 0 ; for ( int k = 0 ; k < v1.get(i).length; k++) { res += v1.get(i)[k] & v1.get(j)[k]; } if (res == Arrays.stream(v1.get(i)).sum()) { flag = true ; } } } if (!flag) { ans.add(i); } } return ; } public static void main(String[] args) { String[][] v = {{ "hey" , "hello" , "hi" }, { "hey" , "bye" }, { "hey" , "hi" }}; List<Integer> ans = new ArrayList<>(); findNonSubsets(v, ans); if (ans.size() == 0 ) { System.out.println(- 1 ); return ; } System.out.println(ans.toString().replaceAll( "\\[|\\]|," , "" )); } } |
Python3
from typing import List from collections import defaultdict N = 50005 def findNonSubsets(v: List [ List [ str ]]) - > List [ int ]: mp = defaultdict( int ) id = 1 # Enumerate all strings # present in all lists for i in range ( len (v)): for j in range ( len (v[i])): if mp[v[i][j]] > 0 : continue mp[v[i][j]] = id id + = 1 # Compute and store bitsets # of all strings in lists v1 = [] for i in range ( len (v)): b = [ 0 ] * N for j in range ( len (v[i])): b[mp[v[i][j]]] = 1 v1.append(b) ans = [] for i in range ( len (v)): flag = False for j in range ( len (v)): if i ! = j: # If one of the bitsets is # a subset of another, the # logical AND is equal to the # subset(intersection operation) if all (v1[i][k] and v1[j][k] for k in range ( 1 , id )): flag = True if not flag: ans.append(i) return ans # Driver Program if __name__ = = "__main__" : v = [[ "hey" , "hello" , "hi" ], [ "hey" , "bye" ], [ "hey" , "hi" ]] ans = findNonSubsets(v) if len (ans) = = 0 : print ( - 1 ) else : print ( * ans) |
C#
using System; using System.Collections.Generic; class MainClass { // C# implementation to find all lists which are not a subset of any other given lists public static void FindNonSubsets( string [][] v, List< int > ans) { Dictionary< string , int > mp = new Dictionary< string , int >(); int id = 1; // Enumerate all strings present in all lists foreach ( string [] subList in v) { foreach ( string item in subList) { if (!mp.ContainsKey(item)) { mp[item] = id++; } } } // Compute and store bitsets of all strings in lists List< int []> v1 = new List< int []>(); foreach ( string [] subList in v) { int [] b = new int [id]; foreach ( string item in subList) { b[mp[item]] = 1; } v1.Add(b); } for ( int i = 0; i < v.Length; i++) { bool flag = false ; for ( int j = 0; !flag && j < v.Length; j++) { if (i != j) { // If one of the bitsets is a subset of another, the logical AND is equal to the subset (intersection operation) int res = 0; for ( int k = 0; k < v1[i].Length; k++) { res += v1[i][k] & v1[j][k]; } if (res == Array.FindAll(v1[i], x => x == 1).Length) { flag = true ; } } } if (!flag) { ans.Add(i); } } } public static void Main( string [] args) { string [][] v = { new string [] { "hey" , "hello" , "hi" }, new string [] { "hey" , "bye" }, new string [] { "hey" , "hi" } }; List< int > ans = new List< int >(); FindNonSubsets(v, ans); if (ans.Count == 0) { Console.WriteLine(-1); return ; } Console.WriteLine( string .Join( " " , ans)); } } |
Javascript
// JavaScript implementation to find all lists which are not a subset of any other given lists const findNonSubsets = (v, ans) => { const mp = new Map(); let id = 1; // Enumerate all strings present in all lists for (let i = 0; i < v.length; i++) { for (let j = 0; j < v[i].length; j++) { if (mp.has(v[i][j])) continue ; mp.set(v[i][j], id++); } } // Compute and store bitsets of all strings in lists const v1 = []; for (let i = 0; i < v.length; i++) { const b = []; for (let j = 0; j < v[i].length; j++) { b[mp.get(v[i][j])] = 1; } v1.push(b); } for (let i = 0; i < v.length; i++) { let flag = false ; for (let j = 0; !flag && j < v.length; j++) { if (i !== j) { // If one of the bitsets is a subset of another, the logical AND is equal to the subset (intersection operation) if (v1[i].reduce((acc, curr, idx) => acc + (curr & v1[j][idx]), 0) === v1[i].reduce((acc, curr) => acc + curr)) { flag = true ; } } } if (!flag) { ans.push(i); } } return ; }; const v = [[ "hey" , "hello" , "hi" ], [ "hey" , "bye" ], [ "hey" , "hi" ]]; const ans = []; findNonSubsets(v, ans); if (ans.length === 0) { console.log(-1); return ; } console.log(ans.join( " " )); |
Output
0 1
Time Complexity: O ( N * M )
Auxiliary Space: O ( N * M )
Contact Us