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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
        

Solutions:
class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		result = []
		fcSet = [set(fc) for fc in favoriteCompanies]
		n = len(favoriteCompanies)
		for (i, fcs1) in enumerate(fcSet):
			for (j, fcs2) in enumerate(fcSet):
				if i == j:
					continue
				if fcs1 < fcs2:
					break
			else:
				result.append(i)
		return result


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		n = len(favoriteCompanies)
		res = list(range(n))
		array_of_sets = [set(company) for company in favoriteCompanies]
		for i in range(n):
			for j in range(n):
				if i != j:
					if array_of_sets[i].issubset(array_of_sets[j]):
						res.remove(i)
						break
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		result = []
		for x in range(0, len(favoriteCompanies)):
			flag = True
			for y in range(0, len(favoriteCompanies)):
				if x == y:
					continue
				setx = set(favoriteCompanies[x])
				sety = set(favoriteCompanies[y])
				if setx.issubset(sety):
					flag = False
					break
			if flag:
				result.append(x)
		return sorted(result)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		return [i for (i, s1) in enumerate(favoriteCompanies) if not any((set(s1).issubset(s2) for s2 in favoriteCompanies if s1 is not s2))]


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		A = favoriteCompanies
		location = {tuple(val): idx for (idx, val) in enumerate(A)}
		A.sort(key=lambda x: len(x))
		res = []
		for i in range(len(A)):
			for j in range(i + 1, len(A)):
				if set(A[i]) & set(A[j]) == set(A[i]):
					break
			else:
				res.append(location[tuple(A[i])])
		res.sort()
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		order = {tuple(value): idx for (idx, value) in enumerate(favoriteCompanies)}
		favoriteCompanies = sorted(favoriteCompanies, key=len, reverse=True)
		ans = []
		visited = []
		for fav in favoriteCompanies:
			find = 0
			for v in visited:
				if set(v) & set(fav) == set(fav):
					find = 1
					break
			if find == 0:
				visited.append(fav)
				ans.append(order[tuple(fav)])
		return sorted(ans)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		l = [0] * len(favoriteCompanies)
		p = []
		for i in range(len(favoriteCompanies)):
			if l[i] == 0:
				p.append(i)
				temp = set(favoriteCompanies[i])
				for j in range(i + 1, len(favoriteCompanies)):
					if temp & set(favoriteCompanies[j]) == temp:
						l[i] = 1
						p[-1] = j
						temp = set(favoriteCompanies[j])
					elif temp & set(favoriteCompanies[j]) == set(favoriteCompanies[j]):
						l[j] = 1
		p = set(p)
		p = list(p)
		p.sort()
		return p


class Solution:

	def peopleIndexes(self, com: List[List[str]]) -> List[int]:
		c = com[:]
		com.sort(key=lambda x: -len(x))
		index = 1
		while index < len(com):
			curr = set(com[index])
			if any((set(com[i]) & curr == curr for i in range(index))):
				com.pop(index)
			else:
				index += 1
		res = []
		for i in com:
			for j in range(len(c)):
				if i == c[j]:
					res.append(j)
		return sorted(res)


class Solution:

	def peopleIndexes(self, fav: List[List[str]]) -> List[int]:
		l = []
		l1 = []
		for i in range(len(fav)):
			for j in range(len(fav)):
				if j is not i and set(fav[i]).issubset(set(fav[j])):
					l.append(i)
		for i in range(len(fav)):
			if i not in l:
				l1.append(i)
		return l1


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		fev_set = []
		for i in favoriteCompanies:
			tmp = set()
			for j in i:
				tmp.add(j)
			fev_set.append(tmp)
		ans = []
		for (ind, i) in enumerate(fev_set):
			flag = 0
			for (i2, j) in enumerate(fev_set):
				if i2 != ind and i <= j:
					flag = 1
					break
			if not flag:
				ans.append(ind)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:

		def isSubset(lst1, lst2):
			if len(lst1) > len(lst2):
				return False
			largerSet = set()
			for elt in lst2:
				largerSet.add(elt)
			for elt in lst1:
				if elt not in largerSet:
					return False
			return True
		return [i for i in range(len(favoriteCompanies)) if not any((j != i and isSubset(favoriteCompanies[i], favoriteCompanies[j]) for j in range(len(favoriteCompanies))))]


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		res = []
		l = len(favoriteCompanies)
		for i in range(l):
			f = 0
			for j in range(l):
				if i != j:
					if set(favoriteCompanies[i]).issubset(set(favoriteCompanies[j])):
						f = 1
						break
			if f == 0:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, fc: List[List[str]]) -> List[int]:

		def helper(s, b):
			return len(set(s).intersection(set(b))) == len(s)
		n = len(fc)
		out = []
		for i in range(n):
			f = fc.pop(0)
			for rest in fc:
				if helper(f, rest):
					out.append(i)
					break
			fc.append(f)
		return sorted(list(set(range(n)).difference(set(out))))


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		no_overlap = []
		for i in range(len(favoriteCompanies)):
			flag = True
			for j in range(len(favoriteCompanies)):
				if i == j:
					continue
				if len(set(favoriteCompanies[i]) - set(favoriteCompanies[j])) == 0:
					flag = False
					break
			if flag:
				no_overlap.append(i)
		return no_overlap


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ret = []
		for (ind, current_person) in enumerate(favoriteCompanies):
			check = False
			for j in range(len(favoriteCompanies)):
				if ind == j:
					continue
				previous_person = favoriteCompanies[j]
				if len(list(set(current_person) & set(previous_person))) == len(current_person):
					check = True
					break
			if not check:
				ret.append(ind)
		return ret


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		mp = {}
		num_person = len(favoriteCompanies)
		for i in range(num_person):
			p = favoriteCompanies[i]
			for v in p:
				if v not in mp:
					mp[v] = set()
				mp[v].add(i)
		result = []
		for i in range(num_person):
			p = favoriteCompanies[i]
			common = {}
			found = False
			for v in p:
				for k in mp[v]:
					if k not in common:
						common[k] = 0
					common[k] += 1
					if common[k] == len(p) and k != i:
						found = True
						break
				if found == True:
					break
			if found == False:
				result.append(i)
		return result


class Solution:

	def peopleIndexes(self, A: List[List[str]]) -> List[int]:
		A = [set(A[i]) for i in range(len(A))]
		answer = []
		for i in range(len(A)):
			answer.append(i)
			for j in range(len(A)):
				if i != j and len(A[i] | A[j]) == len(A[j]):
					answer.pop()
					break
		return answer


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		LEN = len(favoriteCompanies)
		ans = []
		for i in range(LEN):
			found = False
			for j in range(LEN):
				if i != j:
					s1 = set(favoriteCompanies[i])
					s2 = set(favoriteCompanies[j])
					if len(s1 & s2) == len(s1):
						found = True
			if not found:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		subsets = set()
		res = []
		for i in range(len(favoriteCompanies)):
			for j in range(len(favoriteCompanies)):
				if i != j and set(favoriteCompanies[i]).issubset(favoriteCompanies[j]):
					subsets.add(i)
		for i in range(len(favoriteCompanies)):
			if i not in subsets:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		result = []
		for i in range(len(favoriteCompanies)):
			f = True
			for x in favoriteCompanies[:i] + favoriteCompanies[i + 1:]:
				if set(favoriteCompanies[i]).intersection(set(x)) == set(favoriteCompanies[i]):
					f = False
					break
			if f:
				result.append(i)
		return result


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = []
		for i in range(len(favoriteCompanies)):
			for j in range(len(favoriteCompanies)):
				if i != j:
					if len(set(favoriteCompanies[i]) & set(favoriteCompanies[j])) == len(set(favoriteCompanies[i])):
						break
			else:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = []
		for i in range(len(favoriteCompanies)):
			flag = 0
			for j in range(len(favoriteCompanies)):
				if set(favoriteCompanies[i]) & set(favoriteCompanies[j]) == set(favoriteCompanies[i]) and i != j:
					flag = 1
					break
			if flag == 0:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		dic = collections.defaultdict(list)
		fc = favoriteCompanies
		for (i, p) in enumerate(fc):
			for c in p:
				dic[c].append(i)
		n = len(fc)
		counter = [[0] * n for _ in range(n)]
		for l in dic.values():
			for i in range(len(l)):
				for j in range(i + 1, len(l)):
					counter[l[i]][l[j]] += 1
					counter[l[j]][l[i]] += 1
		ans = set()
		for i in range(n):
			for j in range(n):
				if counter[i][j] == len(fc[i]):
					ans.add(i)
					break
		return sorted(set(range(n)) - ans)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		dic = {}
		ind = 0
		profile = []
		for companies in favoriteCompanies:
			for company in companies:
				if company not in dic:
					dic[company] = ind
					ind += 1
		for companies in favoriteCompanies:
			val = 0
			for company in companies:
				val += 2 ** dic[company]
			profile.append(val)
		res = []
		for i in range(len(profile)):
			flag = True
			for j in range(len(profile)):
				if i == j:
					continue
				elif profile[i] | profile[j] == profile[j]:
					flag = False
					break
			if flag:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		dic_companies = {}
		inx = 0
		for companies in favoriteCompanies:
			for company in companies:
				if company not in dic_companies:
					dic_companies[company] = inx
					inx += 1
		favorite_comp = []
		for companies in favoriteCompanies:
			val = 0
			for company in companies:
				val += 2 ** dic_companies[company]
			favorite_comp.append(val)
		res = []
		for i in range(len(favorite_comp)):
			flag = True
			for j in range(len(favorite_comp)):
				if i == j:
					continue
				if favorite_comp[i] | favorite_comp[j] == favorite_comp[j]:
					flag = False
					break
			if flag:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		for u in favoriteCompanies:
			u.sort()
		L = len(favoriteCompanies)
		dic = {}

		def check(i, j):
			if (i, j) in dic:
				return dic[i, j]
			else:
				stack1 = favoriteCompanies[i].copy()
				stack2 = favoriteCompanies[j].copy()
				while stack1 and stack2:
					if stack2[0] != stack1[0]:
						stack2.pop(0)
					elif stack2[0] == stack1[0]:
						stack1.pop(0)
						stack2.pop(0)
				if not stack1:
					dic[i, j] = True
					return True
				else:
					dic[i, j] = False
					return False
		ans = []
		for i in range(L):
			status = 0
			for j in range(L):
				if j != i and check(i, j):
					status = 1
					break
			if status == 0:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		frequency_dict = dict()
		word_tracker = dict()
		for (index, companies) in enumerate(favoriteCompanies):
			for company in companies:
				if company not in word_tracker:
					word_tracker[company] = []
				for matched_index in word_tracker[company]:
					if matched_index not in list(frequency_dict.keys()):
						frequency_dict[matched_index] = dict()
					if index not in list(frequency_dict[matched_index].keys()):
						frequency_dict[matched_index][index] = 0
					if index not in list(frequency_dict.keys()):
						frequency_dict[index] = dict()
					if matched_index not in list(frequency_dict[index].keys()):
						frequency_dict[index][matched_index] = 0
					frequency_dict[matched_index][index] += 1
					frequency_dict[index][matched_index] += 1
				word_tracker[company].append(index)
		ret_list = []
		for (index, companies) in enumerate(favoriteCompanies):
			is_subset = False
			if index in list(frequency_dict.keys()):
				for key in list(frequency_dict[index].keys()):
					if frequency_dict[index][key] >= len(companies):
						is_subset = True
						break
			if not is_subset:
				ret_list.append(index)
		return ret_list


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		c_id = 0
		h = {}
		for fc in favoriteCompanies:
			for c in fc:
				if c in h:
					continue
				h[c] = c_id
				c_id += 1
		for (idx, fc) in enumerate(favoriteCompanies):
			fc.sort(key=lambda x: h[x])
		N = len(favoriteCompanies)
		ret = []
		for i in range(N):
			for j in range(N):
				if i == j:
					continue
				(ci, cj) = (favoriteCompanies[i], favoriteCompanies[j])
				(iidx, jidx) = (0, 0)
				while iidx < len(ci) and jidx < len(cj):
					iidx += ci[iidx] == cj[jidx]
					jidx += 1
				if iidx == len(ci):
					break
			else:
				ret.append(i)
		return ret


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		a = [set(y) for y in favoriteCompanies]

		def check(i):
			return all([i == j or not a[i].issubset(a[j]) for j in range(len(a))])
		return [i for i in range(len(a)) if check(i)]


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		sets = [set(x) for x in favoriteCompanies]
		for (i, companies) in enumerate(sets):
			for (j, other) in enumerate(sets):
				if i == j:
					continue
				if companies <= other:
					break
			else:
				yield i


class Solution:

	def peopleIndexes(self, favorite_companies: List[List[str]]) -> List[int]:
		company_set_per_person = []
		for (i, company_list) in enumerate(favorite_companies):
			company_set = set(company_list)
			found = False
			for (j, (other_company_set, k)) in enumerate(company_set_per_person):
				if company_set >= other_company_set:
					company_set_per_person[j] = (company_set, i)
					found = True
					break
				if company_set <= other_company_set:
					found = True
					break
			if not found:
				company_set_per_person.append((company_set, i))
		ans = []
		for (i, company_list) in enumerate(favorite_companies):
			company_set = set(company_list)
			found = False
			for (other_company_set, j) in company_set_per_person:
				if company_set <= other_company_set and i != j:
					found = True
					break
			if not found:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		d = {}
		n = len(favoriteCompanies)
		A = []
		for (j, arr) in enumerate(favoriteCompanies):
			A.append((arr, j))
		A.sort(key=lambda x: len(x[0]), reverse=True)
		print(A)
		ans = []
		s1 = set()
		for i in range(n):
			k = A[i][1]
			s1.add(k)
			temp = s1
			for (j, c) in enumerate(A[i][0]):
				if c not in d:
					d[c] = set([k])
				else:
					d[c].add(k)
				temp = temp.intersection(d[c])
			if len(temp) == 1:
				ans.append(k)
		ans.sort()
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		htable = {}
		for (i, j) in enumerate(favoriteCompanies):
			htable[i] = set(j)
		result = []
		for k in htable:
			flag = True
			for j in list(htable.values()):
				if htable[k] == j:
					continue
				elif htable[k].issubset(j):
					flag = False
					break
			if flag:
				result.append(k)
		print(result)
		return result


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		people = []
		sets = [set(Co) for Co in favoriteCompanies]
		for (i, a) in enumerate(sets):
			for (j, b) in enumerate(sets):
				if i == j:
					continue
				if a.issubset(b):
					break
			else:
				people.append(i)
		return people


class Solution:

	def _subset(self, fav, result):
		for x in result:
			if not fav - x:
				return True
		return False

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		favorite_companies = [tuple(sorted(x)) for x in favoriteCompanies]
		val_to_key = {x: i for (i, x) in enumerate(favorite_companies)}
		len_to_comp = collections.defaultdict(list)
		for x in favorite_companies:
			len_to_comp[len(x)].append(set(x))
		sorted_keys = sorted(len_to_comp, reverse=True)
		result = []
		for key in sorted_keys:
			curr = []
			for fav in len_to_comp[key]:
				if not self._subset(fav, result):
					curr.append(fav)
			result += curr
		result = [tuple(sorted(x)) for x in result]
		return sorted([val_to_key[x] for x in result])


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		cs = {w for f in favoriteCompanies for w in f}
		cs = {v: i for (i, v) in enumerate(cs)}
		fs = []
		for f in favoriteCompanies:
			i = 0
			for c in f:
				i |= 1 << cs[c]
			fs.append(i)
		ans = []
		for i in range(len(fs)):
			f = 1
			for j in range(len(fs)):
				if i == j:
					continue
				if fs[i] | fs[j] == fs[j]:
					f ^= 1
					break
			if f:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		res = []
		subsets = sorted([[set(companies), i] for (i, companies) in enumerate(favoriteCompanies)], key=lambda x: len(x[0]))
		for (i, companies) in enumerate(subsets):
			(companies, res_i) = companies
			for (j, companies2) in enumerate(subsets[i + 1:], i + 1):
				companies2 = companies2[0]
				if all((company in companies2 for company in companies)):
					break
			else:
				res += (res_i,)
		return sorted(res)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		favorite_index = collections.defaultdict(set)
		for fav in range(len(favoriteCompanies)):
			for company in favoriteCompanies[fav]:
				favorite_index[company].add(fav)
		result = []
		for fav in range(len(favoriteCompanies)):
			subsets = set()
			first = True
			for company in favoriteCompanies[fav]:
				if first:
					subsets = subsets.union(favorite_index[company])
					first = False
				else:
					subsets = subsets.intersection(favorite_index[company])
				if len(subsets) == 1:
					result.append(fav)
					break
		return result


def comp(a, b):
	for i in a:
		if i not in b:
			return 0
	return 1

class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		favoriteCompanies = [(j, i) for (i, j) in enumerate(favoriteCompanies)]
		x = sorted(favoriteCompanies, key=lambda x: len(x[0]), reverse=True)
		y = [i[1] for i in x]
		x = [i[0] for i in x]
		arrd = []
		for i in range(len(x)):
			d = {}
			for j in range(len(x[i])):
				d[x[i][j]] = 1
			arrd.append(d)
		ind = [0] * len(x)
		for j in range(len(x)):
			for i in range(j - 1, -1, -1):
				if comp(arrd[j], arrd[i]):
					ind[j] = 1
					break
		f = []
		for i in range(len(ind)):
			if ind[i] == 0:
				f.append(y[i])
		return sorted(f)


class Solution:

	def peopleIndexes(self, A: List[List[str]]) -> List[int]:
		d = {i: set(v) for (i, v) in enumerate(A)}
		res = []
		for i in range(len(A)):
			isSubset = False
			for j in range(len(A)):
				if i == j:
					continue
				if d[i].issubset(d[j]):
					isSubset = True
					break
			if not isSubset:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		g = collections.defaultdict(set)
		self.parent = [i for i in range(len(favoriteCompanies))]
		for (i, companies) in enumerate(favoriteCompanies):
			g[i] = set(companies)
		for i in range(len(favoriteCompanies)):
			for j in range(i + 1, len(favoriteCompanies)):
				(a, b) = (self.find(i), self.find(j))
				if a != b:
					if g[a] >= g[b]:
						self.parent[b] = a
					elif g[b] > g[a]:
						self.parent[a] = b
		res = set()
		for i in range(len(favoriteCompanies)):
			res.add(self.find(i))
		return sorted(res)

	def find(self, i):
		while self.parent[i] != i:
			self.parent[i] = self.parent[self.parent[i]]
			i = self.parent[i]
		return i


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		d = {}
		for (ind, company) in enumerate(favoriteCompanies):
			for e in company:
				if e not in d:
					d[e] = set()
				d[e].add(ind)
		output = []
		for (ind, company) in enumerate(favoriteCompanies):
			temp = d[company[0]]
			for e in company[1:]:
				temp = temp.intersection(d[e])
			if len(temp) <= 1:
				output.append(ind)
		return output


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = []
		s = [set(c) for c in favoriteCompanies]
		for (i, s1) in enumerate(s):
			if all((i == j or not s1.issubset(s2) for (j, s2) in enumerate(s))):
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, fv: List[List[str]]) -> List[int]:
		dic = defaultdict(lambda : set())
		for i in range(len(fv)):
			for cmp in fv[i]:
				dic[cmp].add(i)
		ans = []
		ind = 0
		for lst in fv:
			st = None
			for cmp in lst:
				if st:
					st &= dic[cmp]
				else:
					st = dic[cmp].copy()
			if len(st) == 1:
				ans.append(ind)
			ind += 1
		return sorted(ans)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		graph = collections.defaultdict(set)
		for (i, companies) in enumerate(favoriteCompanies):
			for comp in companies:
				graph[comp].add(i)
		ans = []
		for (i, companies) in enumerate(favoriteCompanies):
			groups = None
			for comp in companies:
				if groups is None:
					groups = set((x for x in graph[comp]))
				else:
					groups &= graph[comp]
			if len(groups) == 1:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		companies = favoriteCompanies[:]
		for i in range(len(companies)):
			companies[i] = set(companies[i])
		subsets = []
		for i in range(len(companies)):
			currSet = companies[i]
			for j in range(len(companies)):
				if i != j:
					count = 0
					for each in currSet:
						if each in companies[j]:
							count += 1
						else:
							break
					if count == len(currSet):
						subsets.append(i)
						break
		size = len(favoriteCompanies) - len(subsets)
		res = [None] * size
		curr = 0
		subsets = set(subsets)
		for i in range(len(favoriteCompanies)):
			if i not in subsets:
				res[curr] = i
				curr += 1
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		dict = defaultdict(int)
		for (i, lst) in enumerate(favoriteCompanies):
			people_mask = 1 << i
			for comp in lst:
				dict[comp] += people_mask
		res = []
		for (i, lst) in enumerate(favoriteCompanies):
			other_people = ~(1 << i)
			for comp in lst:
				other_people &= dict[comp]
				if not other_people:
					break
			if not other_people:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		name2idx = {}
		group = {}
		for i in range(len(favoriteCompanies)):
			for item in favoriteCompanies[i]:
				if not item in name2idx:
					name2idx[item] = len(name2idx)
		for i in range(len(favoriteCompanies)):
			favoriteCompanies[i] = [name2idx[x] for x in favoriteCompanies[i]]
		for i in range(len(favoriteCompanies)):
			group[tuple([x for x in favoriteCompanies[i]])] = i
		favoriteCompanies = sorted(favoriteCompanies, key=lambda x: len(x), reverse=True)
		ans = []
		for i in range(len(favoriteCompanies)):
			if len(ans) == 0:
				ans.append(group[tuple([x for x in favoriteCompanies[i]])])
				continue
			cur_set = set(favoriteCompanies[i])
			flag = True
			for j in range(i):
				pre_set = set(favoriteCompanies[j])
				if cur_set.issubset(pre_set):
					flag = False
					break
			if flag:
				ans.append(group[tuple([x for x in favoriteCompanies[i]])])
		ans.sort()
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		res = []
		subsets = [[set(companies), i] for (i, companies) in enumerate(favoriteCompanies)]
		for (i, companies) in enumerate(subsets):
			(companies, res_i) = companies
			for (j, companies2) in enumerate(subsets):
				if i == j:
					continue
				companies2 = companies2[0]
				if all((company in companies2 for company in companies)):
					break
			else:
				res += (res_i,)
		return sorted(res)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		D = collections.defaultdict(int)
		for (i, cs) in enumerate(favoriteCompanies):
			p = 1 << i
			for c in cs:
				D[c] |= p
		res = []
		ac = 2 ** len(favoriteCompanies) - 1
		for (i, cs) in enumerate(favoriteCompanies):
			p = 1 << i
			pc = ac
			for c in cs:
				pc &= D[c]
			if p == pc:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		coms = sorted([[set(cs), oi] for (oi, cs) in enumerate(favoriteCompanies)], key=lambda x: len(x[0]))
		ret = []
		for (i, com) in enumerate(coms):
			(com1, oi) = com
			is_sub = False
			for (com2, _) in coms[i + 1:]:
				if not com1 - com2:
					is_sub = True
					break
			if not is_sub:
				ret.append(oi)
		return sorted(ret)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		if len(favoriteCompanies) == 0:
			return []
		answer = []
		listOfSets = [[set(favoriteCompanies[index]), index] for index in range(len(favoriteCompanies))]
		listOfSets.sort(key=lambda pair: len(pair[0]))
		print(listOfSets)
		for i in range(len(listOfSets)):
			subset = False
			for j in range(i + 1, len(listOfSets)):
				if listOfSets[i][0].issubset(listOfSets[j][0]):
					subset = True
					break
			if subset == False:
				answer.append(listOfSets[i][1])
		answer.sort()
		return answer


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		idx = {}
		encoded = []
		n = len(favoriteCompanies)
		for l in favoriteCompanies:
			b = 0
			for c in l:
				idx.setdefault(c, len(idx))
				b |= 1 << idx[c]
			encoded.append(b)
		ans = []
		for (i, b1) in enumerate(encoded):
			for b2 in encoded:
				if b1 | b2 == b2 and b1 != b2:
					break
			else:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		lst = []
		n = len(favoriteCompanies)
		for i in range(n):
			c = set(favoriteCompanies[i])
			lst.append([c, i])
		lst.sort(key=lambda x: -len(x[0]))
		subset = set()
		for i in range(n - 1, 0, -1):
			for j in range(i - 1, -1, -1):
				if lst[j][0] & lst[i][0] == lst[i][0]:
					subset.add(lst[i][1])
		return [i for i in range(n) if i not in subset]


class Solution:

	def peopleIndexes(self, favorites: List[List[str]]) -> List[int]:
		parents = []
		parent_sets = []
		for i in sorted(range(len(favorites)), key=lambda i: len(favorites[i]), reverse=True):
			c = set(favorites[i])
			is_parent = True
			for p in parent_sets:
				if c.issubset(p):
					is_parent = False
					break
			if is_parent:
				parents.append(i)
				parent_sets.append(c)
		return sorted(parents)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		n = len(favoriteCompanies)
		res = list(range(n))
		seen = set()
		array_of_sets = [set(company) for company in favoriteCompanies]
		for i in range(n - 1):
			for j in range(i + 1, n):
				if i != j:
					remind = array_of_sets[i] & array_of_sets[j]
					if remind == array_of_sets[i]:
						if i not in seen:
							seen.add(i)
							res.remove(i)
					if remind == array_of_sets[j]:
						if j not in seen:
							seen.add(j)
							res.remove(j)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		companies_set = [set(c) for c in favoriteCompanies]
		res = []
		for (i, s1) in enumerate(companies_set):
			is_subset = False
			for (j, s2) in enumerate(companies_set):
				if i == j:
					continue
				if s1.issubset(s2):
					is_subset = True
			if not is_subset:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		length = len(favoriteCompanies)
		for i in range(length):
			favoriteCompanies[i] = set(favoriteCompanies[i])
		res = []
		for i in range(length):
			pattern = favoriteCompanies[i]
			for flist in favoriteCompanies:
				if pattern < flist:
					break
			else:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		glb = set()
		ct = 0
		ds = {}
		for i in favoriteCompanies:
			for j in i:
				if j not in glb:
					ct = ct + 1
					ds[j] = ct
					glb.add(j)
		d = collections.defaultdict(set)
		for i in range(len(favoriteCompanies)):
			new = set()
			for j in favoriteCompanies[i]:
				new.add(ds[j])
			d[i] = new
		ar = []
		for i in range(len(favoriteCompanies)):
			found = 0
			for j in range(len(favoriteCompanies)):
				if i != j:
					x = d[i].intersection(d[j])
					if x == d[i]:
						found = 1
						break
			if found == 0:
				ar.append(i)
		return ar


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		favoriteCompanies = [[len(favoriteCompanies[i]), i, set(favoriteCompanies[i])] for i in range(len(favoriteCompanies))]
		favoriteCompanies.sort()
		res = []
		for i in range(len(favoriteCompanies)):
			attendre = favoriteCompanies[i][2]
			flag = True
			for j in range(i + 1, len(favoriteCompanies)):
				if not attendre - favoriteCompanies[j][2]:
					flag = False
					break
			if flag:
				res.append(favoriteCompanies[i][1])
		return sorted(res)


from collections import defaultdict

class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		out = []
		d = defaultdict(list)
		for (i, companies) in enumerate(favoriteCompanies):
			for company in companies:
				d[company].append(i)
		for (i, companies) in enumerate(favoriteCompanies):
			s = set(d[companies[0]])
			for company in companies:
				s = s.intersection(d[company])
			if len(s) == 1:
				out.append(i)
		return out


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:

		def judge(i):
			for j in range(n):
				if i != j:
					contain = True
					for x in favoriteCompanies[i]:
						if x not in favoriteCompanies[j]:
							contain = False
							break
					if contain:
						return False
			return True
		n = len(favoriteCompanies)
		favoriteCompanies = list(map(set, favoriteCompanies))
		res = []
		for i in range(n):
			if judge(i):
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		favoriteCompanies = [set(i) for i in favoriteCompanies]
		visited = [False] * len(favoriteCompanies)
		res = []
		for i in range(len(favoriteCompanies) - 1):
			if visited[i]:
				continue
			else:
				for j in range(i + 1, len(favoriteCompanies)):
					if favoriteCompanies[i].intersection(favoriteCompanies[j]) == favoriteCompanies[i]:
						visited[i] = True
						break
					elif favoriteCompanies[i].intersection(favoriteCompanies[j]) == favoriteCompanies[j]:
						visited[j] = True
		for i in range(len(favoriteCompanies)):
			if not visited[i]:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, company: List[List[str]]) -> List[int]:
		company = [set(i) for i in company]
		visited = [False] * len(company)
		for i in range(len(company) - 1):
			if visited[i]:
				continue
			root = company[i]
			for j in range(i + 1, len(company)):
				child = company[j]
				if len(root.intersection(child)) == len(root):
					visited[i] = True
					break
				elif len(root.intersection(child)) == len(child):
					visited[j] = True
		res = []
		for i in range(len(visited)):
			if visited[i] == False:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		c = set()
		d = {}
		i = 0
		com = []
		for j in favoriteCompanies:
			cur = set()
			for x in j:
				if x not in d:
					d[x] = i
					i += 1
				cur.add(d[x])
			com += [cur]
		ans = []
		for i in range(len(com)):
			flag = False
			for j in range(len(com)):
				if i != j:
					if com[i].issubset(com[j]):
						flag = True
						break
			if not flag:
				ans += [i]
		return ans


class Solution:

	def peopleIndexes(self, A: List[List[str]]) -> List[int]:
		res = []
		fc = [set(f) for f in A]
		n = len(fc)
		for i in range(n):
			for j in range(n):
				if i != j and fc[i] & fc[j] == fc[i]:
					break
			else:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		comp_dict = {i: set(v) for (i, v) in enumerate(favoriteCompanies)}
		res = []
		for i in range(len(favoriteCompanies)):
			subset = True
			for j in range(len(favoriteCompanies)):
				if i == j:
					continue
				if not comp_dict[i] - comp_dict[j]:
					subset = False
					break
			if subset:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		f_C = []
		for company in favoriteCompanies:
			f_C.append(set(company))
		print(f_C)
		n = len(f_C)
		ans = []
		for i in range(n):
			flag = 1
			for j in range(n):
				if i == j:
					continue
				if f_C[i] & f_C[j] == f_C[i]:
					flag = 0
					break
			if flag == 1:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = []
		n = len(favoriteCompanies)
		f = [set(c) for c in favoriteCompanies]
		for i in range(n):
			for j in range(n):
				if i != j and f[i] & f[j] == f[i]:
					break
			else:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ls = []
		for i in favoriteCompanies:
			ls.append(set(i))
		print(ls)
		ans = []
		for i in range(len(ls)):
			flag = 0
			for j in range(len(ls)):
				if i != j:
					tem = ls[i].intersection(ls[j])
					if tem == ls[i]:
						flag = 1
						break
			if flag == 0:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		from collections import Counter
		words = {}
		subsets = []
		for (i, x) in enumerate(favoriteCompanies):
			for y in x:
				if y not in words:
					words[y] = [i]
				else:
					words[y].append(i)
		for (i, x) in enumerate(favoriteCompanies):
			c = Counter()
			for y in x:
				c.update(words[y])
			for item in c.most_common():
				if item[0] != i:
					if item[1] >= len(x):
						break
					else:
						subsets.append(i)
						break
				elif len(c) == 1:
					subsets.append(i)
		return subsets


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		d = {i: set(v) for (i, v) in enumerate(favoriteCompanies)}
		print(d)
		res = []
		for i in range(len(favoriteCompanies)):
			subSet = True
			for j in range(len(favoriteCompanies)):
				if i == j:
					continue
				if not d[i] - d[j]:
					subSet = False
					break
			if subSet:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		hms = []
		output = []
		for favs in favoriteCompanies:
			hm = set(favs)
			hms.append(hm)
		for i in range(len(favoriteCompanies)):
			good = True
			for j in range(len(favoriteCompanies)):
				if i == j:
					continue
				z = hms[j].intersection(hms[i])
				if z == hms[i]:
					good = False
			if good:
				output.append(i)
		return output


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		n = len(favoriteCompanies)
		favoriteCompanies = [set(elem) for elem in favoriteCompanies]
		ans = []
		for i in range(n):
			not_subset = True
			for j in range(n):
				if i == j:
					continue
				if len(favoriteCompanies[i] - favoriteCompanies[j]) == 0:
					not_subset = False
					break
			if not_subset:
				ans.append(i)
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = [x for x in range(len(favoriteCompanies))]
		for i in range(len(favoriteCompanies)):
			for j in range(i + 1, len(favoriteCompanies)):
				set1 = set(favoriteCompanies[i])
				set2 = set(favoriteCompanies[j])
				if set1.issubset(set2):
					ans[i] = -1
				elif set2.issubset(set1):
					ans[j] = -1
		return [x for x in ans if x >= 0]


class Solution:

	def peopleIndexes(self, favoriteCompanies):
		responses = dict()
		ret = []
		for i in range(len(favoriteCompanies)):
			responses[i] = set(favoriteCompanies[i])
		for (i, resp) in list(responses.items()):
			not_sub = True
			for v in list(responses.values()):
				if resp == v:
					continue
				if resp - v == set():
					not_sub = False
			if not_sub:
				ret.append(i)
		return list(sorted(ret))


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		fav = []
		for f in favoriteCompanies:
			fav.append(set(f))
		n = len(favoriteCompanies)
		rem = set()
		for i in range(n):
			for j in range(i + 1, n):
				if not fav[i] - fav[j]:
					rem.add(i)
				if not fav[j] - fav[i]:
					rem.add(j)
		res = []
		for i in range(n):
			if i not in rem:
				res.append(i)
		return res


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		fcs = [set(fc) for fc in favoriteCompanies]
		ret = []
		for i in range(len(fcs)):
			to_incl = True
			for j in range(len(fcs)):
				if j != i and fcs[i].issubset(fcs[j]):
					to_incl = False
					break
			if to_incl:
				ret.append(i)
		return ret


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		sol = []
		for (i, curr_comps) in enumerate(favoriteCompanies):
			curr_comps = set(curr_comps)
			is_subset = False
			for (j, other_comps) in enumerate(favoriteCompanies):
				if j == i:
					continue
				other_comps = set(other_comps)
				if curr_comps.issubset(other_comps):
					is_subset = True
			if not is_subset:
				sol.append(i)
		return sol


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		ans = []
		favorites = defaultdict(list)
		for (i, person) in enumerate(favoriteCompanies):
			for company in person:
				favorites[company].append(i)
		for (i, person) in enumerate(favoriteCompanies):
			possible_supersets = set(range(len(favoriteCompanies)))
			possible_supersets.remove(i)
			for companies in person:
				possible_supersets = possible_supersets.intersection(set(favorites[companies]))
				if len(possible_supersets) == 0:
					break
			if len(possible_supersets) == 0:
				ans.append(i)
		return ans


class Solution:

	def isSub(self, s1, s2):
		i = 0
		for j in range(len(s2)):
			if s1[i] == s2[j]:
				i = i + 1
			if i == len(s1):
				return True
		return False

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		fc = [(sorted(e), i) for (i, e) in enumerate(favoriteCompanies)]
		fc = sorted(fc, key=lambda x: len(x[0]), reverse=True)
		res = []
		for i in range(len(fc)):
			(s, si) = fc[i]
			found = False
			for j in range(i):
				(ps, sj) = fc[j]
				if self.isSub(s, ps):
					found = True
					break
			if not found:
				res.append(si)
		return sorted(res)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		N = len(favoriteCompanies)
		result = list(range(0, N))
		for i in range(0, N):
			a = set(favoriteCompanies[i])
			for j in range(0, N):
				if i == j or len(a) > len(favoriteCompanies[j]):
					continue
				b = set(favoriteCompanies[j])
				if a.intersection(b) == a:
					result.remove(i)
					break
		return result


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		compfaves = {}
		for (i, faves) in enumerate(favoriteCompanies):
			for comp in faves:
				if not comp in compfaves:
					compfaves[comp] = []
				compfaves[comp].append(i)
		outarr = []
		for (i, faves) in enumerate(favoriteCompanies):
			matches = {}
			for comp in faves:
				for person in compfaves[comp]:
					if not person in matches:
						matches[person] = 0
					matches[person] += 1
			issubset = False
			for (p, c) in list(matches.items()):
				if len(faves) == c and p != i:
					issubset = True
					break
			if not issubset:
				outarr.append(i)
		return outarr


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		yu = []
		for j in range(len(favoriteCompanies)):
			a = favoriteCompanies[j]
			yu1 = list(favoriteCompanies)
			yu1.pop(j)
			if any((set(a).issubset(set(ele)) for ele in yu1)) == False:
				yu.append(j)
		return yu


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		n = len(favoriteCompanies)
		res = set()
		for i in range(n - 1):
			for j in range(i + 1, n):
				first_set = set(favoriteCompanies[i])
				second_set = set(favoriteCompanies[j])
				remind = first_set & second_set
				if remind == first_set:
					res.add(i)
				if remind == second_set:
					res.add(j)
		return sorted(list(set(range(n)) - res))


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		i = 0
		ans = []
		while i < len(favoriteCompanies):
			if all((not set(favoriteCompanies[i]).issubset(favoriteCompanies[j]) for j in range(len(favoriteCompanies)) if i != j)):
				ans.append(i)
			i += 1
		return ans


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		company = []
		for (i, fc) in enumerate(favoriteCompanies):
			company.append((tuple(fc), len(fc), i))
		company.sort(key=lambda x: -x[1])
		maxlen = company[0][1]
		loc = -1
		res = []
		for i in range(len(company)):
			if company[i][1] == maxlen:
				res.append(company[i][2])
				loc = max(loc, i)
			else:
				break
		for i in range(loc + 1, len(company)):
			curr = company[i][0]
			flag = 0
			for j in range(i - 1, -1, -1):
				tmpt = company[j][0]
				if set(curr) & set(tmpt) == set(curr):
					flag = 1
			if flag == 0:
				res.append(company[i][2])
		return sorted(res)


class Solution:

	def peopleIndexes(self, favoriteCompanies: List[List[str]]) -> List[int]:
		return [pid for pid in range(len(favoriteCompanies)) if all((not set(favoriteCompanies[pid]).issubset(s) for s in [a for a in favoriteCompanies if a != favoriteCompanies[pid]]))]