This is one of Interview Question.
You are given the string of a's and b's, eg. aaabbbaa and some threshold value t which indicates the threshold point, eg if count of a's or count of b's will become equal to t then whose count will be equal to t eg. a or b will win that match, and next game will continue further, eg from that index of a and b new count values will be incremented, and the process will continue, and at the last you have tell who won the match, a or b.
Expected time complexity: O( n*log(n)*log(n) ).
Why not O(N)?
Yes, I also thought the way that just maintain count of a and b and then check for threshold and later initialise the counts of a and b again( also increment the winner and at the end choose the winner ).
However, I have seen two-three links which propose it to do using dp and binary search, so I thought I am missing something crucial.
I think you may be missing something crucial in the problem statement rather than the solution. The solution you have given is fine for the question you have given. However, I suspect the problem may be harder than the one you have described.
Would you care to share any sort of link for the problem please?
Link
Thanks! Heh, I wouldn't worry too much about it then :) It doesn't seem like that interesting of a problem anyway. I am trying to think of solutions with that complexity and it seems just stupid.
If you want to take something from this, maybe consider a problem with updates to the array, and you query the answer within a range, given that T is small.
Thanks man.
Red Coder _/\_I don't know how to arrive at O( n*log(n)*log(n)), as the statement did not mention what n is.
But if you were to tweak the problem and instead have multiple queries with non-fixed t, then you can have a solution with dp and binary search.