Reverse a String using Stack

The problem, simply

You get a string, like hello. Give back the same letters in the opposite order, olleh. Use a stack to do it: a pile where the last thing you put on is the first thing you take off.

Every character counts, including spaces and punctuation.

A story to remember it

Picture it

Examples

Way 1: the simple way

The first idea many people write is: start with an empty result, and put each new letter in front of it.

1. result = "".
2. For each letter c from left to right: result = c + result.

class Solution {
    public String reverse(String s) {
        String result = "";
        for (char c : s.toCharArray()) {
            result = c + result;          // makes a whole new string every time
        }
        return result;
    }
}

How long it takes: Java strings cannot change, so c + result copies all the letters so far into a new string. That is 1 + 2 + ... + n copies, O(n^2). Extra room: O(n) for the result at any moment.

Way 2: the clever way

Use a stack.

1. Push every letter, from left to right.
2. Pop letters until the stack is empty, appending each one to a StringBuilder.
3. The builder holds the reversed string.

import java.util.*;

class Solution {
    public String reverse(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            stack.push(c);                       // the last letter ends up on top
        }
        StringBuilder out = new StringBuilder(s.length());
        while (!stack.isEmpty()) {
            out.append(stack.pop());             // comes off in reverse order
        }
        return out.toString();
    }
}

How long it takes: each letter is pushed once and popped once, O(n). StringBuilder adds at the end without copying everything, so appending is O(1) on average. Extra room: the stack holds n letters, O(n).

Another way: two pointers, no stack

If the interviewer allows it, you do not need a stack at all. Put one finger on the first letter and one on the last, swap them, and move both fingers toward the middle.

class Solution {
    public String reverse(String s) {
        char[] a = s.toCharArray();
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            char t = a[i];
            a[i] = a[j];                  // swap the two ends
            a[j] = t;
        }
        return new String(a);
    }
}

This is O(n) time. Besides the char array that Java needs anyway because strings cannot change, it uses O(1) extra room. If you are given a char[] to reverse in place, this is the best answer.

Watch out for

• Characters outside the basic range, such as many emoji, take two chars in Java. Reversing char by char splits them apart and breaks them. For such text, reverse by code points, for example new StringBuilder(s).reverse(), which keeps those pairs together.
• Using Stack<Character>. It works, but ArrayDeque is faster and is the modern choice.
• Forgetting the empty string. All three ways handle it, so say so out loud in the interview.

What interviewers ask next

• Reverse the order of words: the sky is blue becomes blue is sky the. Push whole words onto a stack and pop them, or reverse the whole string and then reverse each word.
• Reverse each word but keep the word order: push letters until a space, then pop them all into the output.
• Check if a string is a palindrome. Compare it with its reverse, or move two fingers toward the middle and stop at the first mismatch, O(1) extra room.
• Reverse a string with recursion. reverse(s) = reverse(s.substring(1)) + s.charAt(0). It is a nice idea but O(n^2) because of the copies, and it can overflow the call stack.

Remember this

Grown-up words: the tube is a stack (last in, first out), dropping in is push, tipping out is pop, the two fingers are the two pointer technique, and StringBuilder is a growable string buffer.