344. Reverse String - cocoder39/coco39_LC GitHub Wiki

for a simple question like this, you are asked to solve it in different ways. One simple way is using two pointers to swap whose time complexity is O(n)

solution below uses divide-and-conquer, t(n) = 2t(n / 2) + O(n) = O(n * log n)

string reverseString(string s) {
        if (s.empty() || s.length() == 1) {
            return s;
        }
        
        string part1 = reverseString(s.substr(0, s.length() / 2));
        string part2 = reverseString(s.substr(s.length() / 2, s.length() - s.length() / 2));
        return part2 + part1;
    }