@shuhuixian I think it is important to be rigorous here, cuz the original sorting algorithm make sense here when each substring is not that long, or in other words len(str)<15. We all agree that sorting like 10 chars is constant.
In the real interview, we should ask more clarification for the given assumption. Time complexity is really a case by case term. At least for this question, sorting solution has the best performance, the reason under the hood is len(str)<15.