I think this is just Python's inefficiency on string processing or some issue with the execution infrastructure.

Many people are getting the segmentation faults. In my case tests #3, #4, #8 and #12 are giving the segmentation faults. My submission: https://www.hackerrank.com/challenges/contacts/submissions/code/28219710

I am pretty sure if you use another language, it will just work. :-/ I am reporting this issue to the mods.

EDIT: yup, just rewrote the solution in Golang and got AC. https://www.hackerrank.com/challenges/contacts/submissions/code/28221779