Hello CF's . I was trying to find some optimizations to the this problem

So we have n strings , we are trying to find all rare subsets of theses strings.

a rares subset is a subset x of a string s, such that the number of appearances of x in all strings is strictly lower than a number min_appear .

example :

let's say we have 3 strings and min_appear = 2

abcd abc cde

than the answer is e,ad,bd,ce,de,abc,abd,bcd,abcd,cde (because the number of their appearances = 1 < 2)

these are all the possible subsets and their number of appearances { a=2 ,b=2 ,c=3 ,d=2 ,e=1 ,ab=2 ,ac=2 ,ad=1 ,bc=2 ,bd=1 ,cd=2 ,ce=1 ,de=1 ,abc=2 ,abd=1,bcd=1,abcd=1,cde=1}

The best solution i come with have a n*2^(length of taller string) , i'm wondering if there is a solution with a better complexity.

UDP : Sorry i forgot about subsets of length 3 and 4 .