I was able to come up with the solution and code it interviewer told me it can be done in o(n) time complexity (n is length of string). I am sure it can't be done in less than o(n) . interviewer was adamant and arrogant and factually wrong. not sure what to do in such cases