I was asked to write a program for reversing a string in java using brute force method. I wrote the very general answer which uses string length and charAt() in a for loop. This method has O(n) time complexity, so I was asked to reduce its time complexity. We can use two counters, one running from first position of the string and second from last position of the string running till the middle position of the string, construct two reversed substrings which can then be concatenated to produce complete reversed string. But this will give only O(n/2) which is same as O(n). Are there any another approach to reduce the time complexity for the above program?
Please describe your approach in the below comments section.
