Whether that's over-engineering or not really depends on the data. For this particular interview question we might assume we have very little data to process, but real applications might want to scale that to a point where you actually care about performance (MMO permutation palindrome checker or whatnot).

Personally, I'd use the simplest implementation as a reference, and use it to test more optimised solutions if I ever need them.