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 subset of letters of theses strings.
a rares subset is a subset of letters 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 subset of letters 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 . also each two different letters from each string are distinct.