This question is asked by Google. Given a string, reverse all of its characters and return the resulting string.

Ex: Given the following strings...

“Cat”, return “taC”
“The Daily Byte”, return "etyB yliaD ehT”
“civic”, return “civic”

Thinking about the problem in real life (when possible) always seems to help. If you were asked to reverse a sequence of characters on paper, one of the approaches you might opt to take could involve moving backwards through the sequence, one letter at a time, concatenating (joining) characters together. Let’s start there and see what that kind of solution might look like

public String reverse(String s) {
    String reversed = "";
    for (int i = s.length() - 1; i >= 0; i--) {
        reversed += s.charAt(i);
    }

    return reversed;
}

While this solution works, it’s not very performant due to strings being immutable in Java (immutable is just a scary word that means cannot be changed). Because strings are immutable, every time we add a new character to the string an entirely new copy of that string is made containing the new character. Realizing this pitfall, we can improve our solution by first initializing a buffer to hold our reversed string before returning the result. The only thing that’s left to do is use a variable to store the index where we should place the next character. This variable will be incremented as we walk along the string in reverse to ensure we place the last character in the first position, the second to last character in the second position, so on and so forth. The resulting code is as follows…

public String reverse(String s) {
    char[] characters = new char[s.length()];
    int j = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        characters[j++] = s.charAt(i);
    }

    return new String(characters);
}

Big-O Analysis

Runtime: O(N) where N is the number of characters in our string s (because we only have to scan the string once to reverse it)
Space complexity: O(N) as well (because we must create a new string with N characters in it to solve the problem).