hulk_baba's blog

By hulk_baba, history, 4 years ago, In English

Please go through this problem 716B. My idea is : 1. if length of string in less than 26 , print "-1" and return ; 2. calculate frequency of first 26 characters and then see how many characters are left out and how many '?' are available . 3. If left out == cnt['?'] it is possible. 4. If not go for next 26. 4. I tried it but failed on 18th test case here? Could you help me with my implementation. Or if you have more elegant implementation please suggest me.

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

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In m u maintain amount of symbols on suffix, not on a substring. If i understood correctly

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I made that mistake instead of running upto n I also tried counting symbols upto 26 .But that also failed locally on my system. Don't know what to do.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No answers yet?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any help please...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

here u are ..
link for your accepted code
what you were doing wrong was mapping all the characters of the string in one go rather than dealing with substring of length 26.
just have a look to changes i made.
i cannot say whether mine is elegant or not.
but you can refer mine too link for my accepted code

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First of all, thank you. That was really helpfull. I also tried to do the same where you found count of every letter in a window of 26 , I once store count of first 26 and next time just decreased i-1 and increase i+26 character's count. I realised earlier, I made two mistakes :- 1. Did the counting wrong instead of n i should have used upto 26. 2. updated the wrong indices.