Valeri_Stanchev's blog

Interesting problem about strings :)
By Valeri_Stanchev, history, 11 years ago, In English

Hello everybody,

I need your help! Given a string S (|S| <= 10^5) consisting of uppercase letters and an integer K (K <= |S|). Consider a set consisting of all uppercase letters. We are to choose some letters from that set and replace their occurences in S with a star ('*'). Our goal is to make at least one star appear in each substring of length K and we need to do this choosing minimum number of different letters from the set. Output the minimum number of letters and the letters in different lines. If multiple solutions exist, we can print any of them. For example, if S="ABA" and K=2, then we can choose either 'A' or 'B' and receive "*B*" and "A*A" respectively.

Thanks in advance! :)

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

OK, it was overkill

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

does O(26 * 2 ^ 26) solution become accept ?

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

For each K sized subsequences(there are N — K + 1 of them) find the mask of the letters that does not occur in that subsequence. Lets call them bad subsets.

Afterwards you need to eliminate all the subsets which is subset of one of the above bad subsets. We can do this by somekind of top bottom dp approach which leads to O((2^26 + N)26) complexity. It might be possible to eliminate factor 26. I did not think about it enoubh yet.

→ Reply