Send your feedback or ask for help here!
doc type! = htmlshell09 Codingame
Got to level 5. Studying with mimo
I really understood this puzzle. Go on and make some more!
This puzzle got me thinking…
The naive approach is relatively simple to implement but immediately falls in the big strings. So I went back to the drawing board.
I divided the puzzle to two problems: (1) find all palindromes in the given string, and (2) find all possible decompositions
Took some thinking, then I came up with a nice solution for (1) that executed fast enough.
I also came up with a solution for (2) which was almost(!) good enough. it solved all cases but the “long a” (a string of length 4000, all characters are ‘a’). This is of course a worst-case scenario, and I couldn’t find a generic algo that would solve it in the given time constraint. I ended up treating a uniform string as a special case, providing a mathematical formula based on the length of the string.
Submitted and got 100%
BUT (!!!) I keep thinking that this is not the “right” solution. I can easily see cases where my algo will not execute within the time constraints.
- Well crafted puzzle. I enjoyed it
- What’s the complexity for the worst-case (uniform string) of the best possible algo? (actually, what would be considered here the best possible algo?)