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 d,ad,bd,ce,de (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=1 ,ab=2 ,ac=2 ,ad=1 ,bc=2 ,bd=1 ,cd=2 ,ce=1 ,de=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.