Formatted question description: https://leetcode.ca/all/1452.html

1452. People Whose List of Favorite Companies Is Not a Subset of Another List (Medium)

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

 

Example 1:

Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4] 
Explanation: 
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. 
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. 
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

Example 2:

Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1] 
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].

Example 3:

Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]

 

Constraints:

  • 1 <= favoriteCompanies.length <= 100
  • 1 <= favoriteCompanies[i].length <= 500
  • 1 <= favoriteCompanies[i][j].length <= 20
  • All strings in favoriteCompanies[i] are distinct.
  • All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
  • All strings consist of lowercase English letters only.

Related Topics:
String, Sort

Solution 1.

// OJ: https://leetcode.com/problems/people-whose-list-of-favorite-companies-is-not-a-subset-of-another-list/

// Time: O(NM + N^2) where N is the length of A and M is the maximum length of A[i]
// Space: O(NM)
class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& A) {
        int id = 0, N = A.size();
        vector<bitset<50000>> v;
        unordered_map<string, int> m;
        for (auto &p : A) {
            bitset<50000> bs;
            for (auto &c : p) {
                if (m.count(c) == 0) m[c] = id++;
                bs.set(m[c]);
            }
            v.push_back(bs);
        }
        vector<int> ans;
        for (int i = 0; i < N; ++i) {
            int j = 0;
            for (; j < N; ++j) {
                if (i == j) continue;
                if ((v[i] | v[j]) == v[j]) break;
            }
            if (j == N) ans.push_back(i);
        }
        return ans;
    }
};

Java

class Solution {
    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        for (List<String> list : favoriteCompanies)
            Collections.sort(list);
        List<Integer> indices = new ArrayList<Integer>();
        int peopleCount = favoriteCompanies.size();
        for (int i = 0; i < peopleCount; i++) {
            boolean flag = true;
            List<String> list1 = favoriteCompanies.get(i);
            for (int j = 0; j < peopleCount; j++) {
                if (i == j)
                    continue;
                List<String> list2 = favoriteCompanies.get(j);
                if (isSubset(list1, list2)) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                indices.add(i);
        }
        return indices;
    }

    public boolean isSubset(List<String> list1, List<String> list2) {
        int size1 = list1.size(), size2 = list2.size();
        if (size1 > size2)
            return false;
        int index1 = 0, index2 = 0;
        while (index1 < size1 && index2 < size2) {
            if (list1.get(index1).equals(list2.get(index2)))
                index1++;
            index2++;
        }
        return index1 == size1;
    }
}

All Problems

All Solutions