Any optimzations to this problem ?

Revision en5, by d4rkc0de, 2015-12-17 11:49:31

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.

Tags optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English d4rkc0de 2015-12-17 11:49:31 31
en4 English d4rkc0de 2015-12-17 09:01:28 68
en3 English d4rkc0de 2015-12-17 08:48:16 109
en2 English d4rkc0de 2015-12-17 00:34:18 7
en1 English d4rkc0de 2015-12-17 00:16:11 790 Initial revision (published)