Dadas N listas de strings, a tarefa é encontrar a contagem de listas que não são sublistas de nenhuma outra lista fornecida.
Exemplos: 
 

Entrada: [[“hey”, “hi”, “hello”], [“hey”, “bye”], [“hey”, “hi”]] 
Saída:
Explicação 
A terceira lista é um subconjunto da primeira lista, portanto, a primeira e a segunda lista são as listas necessárias. 
Entrada: [[“geeksforgeeks”, “geeks”], [“geeks”, “geeksforgeeks”]] 
Saída:
Explicação: Ambas as listas são compostas pelo mesmo conjunto de strings. 
 

Abordagem 
Siga as etapas abaixo para resolver o problema: 
 

  1. Em primeiro lugar, enumere todas as strings possíveis em todos os vetores, ou seja, atribua-lhes um número inteiro.
  2. Em seguida, use um Bitset para todas as listas individuais para armazenar as strings presentes nelas.
  3. Compare os bitsets. Se um dos bitsets for um subconjunto de outro, ignore essa lista. Caso contrário, insira o índice dessa lista em um conjunto.
  4. Imprima todos os índices do conjunto.

O código abaixo é a implementação da abordagem acima:
 

// 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;
}
Saída: 
0 1

 

Complexidade de tempo: O (N * M)  
Espaço auxiliar: O (N * M)