Reverse a String

The problem, simply

You get a word, like hello. Give back the same letters in the opposite order: olleh.

There are two common versions. One gives you a String and wants a new String back. The other gives you a char[] and wants you to turn it around in place, without a second array.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build a brand new word. Walk the old word from the last letter to the first and add each letter to the end of the new word.

1. Make an empty StringBuilder.
2. For i from the last index down to 0, append s.charAt(i).
3. Turn the builder into a String.

class Solution {
    public String reverseString(String s) {
        StringBuilder reversed = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            reversed.append(s.charAt(i));   // last letter goes first
        }
        return reversed.toString();
    }
}

How long it takes: one walk over the word, O(n). Extra room: a second word as long as the first, O(n). In Java a String can never be changed, so when the input is a String, this extra copy cannot be avoided.

Way 2: the clever way

When you get a char[], you can turn it around inside itself, like the kids in the line.

1. Put left on the first box and right on the last box.
2. While left < right, swap the two letters.
3. Move left one step right and right one step left.
4. Stop when they meet or cross.

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];   // hold one letter in your spare hand
            s[left] = s[right];
            s[right] = temp;
            left++;                // both fingers walk toward the middle
            right--;
        }
    }
}

How long it takes: about n / 2 swaps, which is still O(n). Extra room: two fingers and one spare letter, O(1).

Another way: recursion

Swap the two ends, then ask a helper to turn around the part in between. The helper does the same with a smaller part, until the part has one letter or none.

class Solution {
    public void reverseString(char[] s) {
        reverse(s, 0, s.length - 1);
    }

    private void reverse(char[] s, int left, int right) {
        if (left >= right) return;        // one letter or none: done
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        reverse(s, left + 1, right - 1);  // helper handles the middle
    }
}

This is still O(n) time, but every waiting helper sits on the call stack, so it needs O(n) extra room. A very long word can overflow the stack. The version reverse(s.substring(1)) + s.charAt(0) is worse: each substring and + copies the word, so it takes O(n^2) time.

Watch out for

• Trying to change a String in place. Java strings cannot change. Use toCharArray() or a StringBuilder.
• Building the answer with result = result + c in a loop. Every + makes a new string and copies all letters, so the loop is O(n^2).
• The empty string. right starts at -1, the loop does not run, and that is fine.
• Emoji and some rare symbols use two char values in Java. Swapping single chars splits them. new StringBuilder(s).reverse() keeps those pairs together.

What interviewers ask next

• Reverse the words in a sentence, like the sky is blue to blue is sky the. Reverse the whole string, then reverse each word again.
• Reverse only the letters and leave digits and symbols where they are. Same two fingers, but each finger skips boxes that are not letters.
• Reverse every block of k letters. Run the same swap loop on each block from i to min(i + k, n) - 1.
• Is a string a palindrome? Same two fingers, but compare instead of swap, and stop at the first mismatch.

Remember this

Grown-up words: the two fingers are the two pointer technique, turning around inside the same boxes is in place reversal, the spare hand is a temporary variable, and the helpers waiting on each other are the recursion call stack.