Welcome to JavaRanch
I am not convinced you have asked that in the correct forum.
We don't give out that sort of answer; please tell us what you thought the correct answer was, and we'll tell you what we think of it.
You are correct Gabriel. I also couldn't think of any better than O(n) but interviewers in general, don't ask a question where complexity is evident. I guess he/she might have provided more inputs which are missing from this post .
Note that Rovart did not give us any real information to go on, so asking for the "optimized" approach is not really useful. However, on the theory that optimized could imply elapsed time optimization (different from complexity), then there could be a divide and conquer optimization for both compression and decompression on a multi-cpu system. Whether this would be valuable or not would depend on a lot of other factors, and I would think that a good interviewer would probably be really interested in hearing what factors the candidate came up with that might make a difference.
As for the complexity of the code - a valid interview question can be asking if a provided solution can be optimized better even when the interviewer knows that it cannot. Personally I would only ask such a question if I was face to face with a person who is doing well in the interview - I would want to be able to judge how stressed they are before asking the question (if they are stressed then the question is a big no-no) and I would want to watch for any signs of stress and be able to pull them away from going down a rabbit hole. But if they are good then they may be able to see that there are no improvements possible. (I did get asked how I could improve a solution one time where the interviewer wanted to see if I would jump to a JNI solution).
Depending on whether the characters can repeat or not, your solution would vary a little. You cannot however compress / decompress better than O(N) since you need to go through the entire string to understand how to build the output string.