StackEasyO(n) time · O(n) space

Reverse a String

Ramayana — Sita's Mirror — Reading the Sacred Message Backwards

प्रथमं अन्तिमं भवति, अन्तिमं प्रथमं। भण्डारागारे संग्रहीत्वा — विपरीतक्रमेण निर्गच्छेत्॥

*The first becomes last, the last becomes first. Store in the treasury — then release in reverse order.*

The Story

Reverse a string using a stack. This is the canonical demonstration of the stack's LIFO (Last In, First Out) property.

For `s = "abcde"`, return `"edcba"`.

Sita encoded a message for Rama. To prevent Ravana from reading it, every character was stored in a stack (the sacred treasury). Then each character was retrieved last-in-first-out — naturally reversing the original order.

**Stack approach:** 1. Push each character onto the stack 2. Pop each character — they come out in reverse order 3. Build the result string from popped characters

Trace `"hello"`: - Push: h, e, l, l, o → stack = [h, e, l, l, o] (o on top) - Pop: o, l, l, e, h - Result: `"olleh"`

**Why this matters as a stack problem:** While reversing a string has simpler O(1) space methods (two-pointer swap), using a stack illustrates the core LIFO property that powers more complex stack problems. The stack naturally reverses the order of anything pushed into it.

**Alternative O(1) space:** Two-pointer approach — swap chars from both ends toward the center.

This is the "Hello World" of stack problems — simple enough to understand the mechanics, profound enough to reveal the pattern.

The Two-Pointer Approach

Convert to char array. Swap characters from both ends inward. O(n) time, O(n) for char array.

java

String reverseTwoPointer(String s) {
    char[] arr = s.toCharArray();
    int left = 0, right = arr.length - 1;
    while (left < right) {
        char temp = arr[left];
        arr[left++] = arr[right];
        arr[right--] = temp;
    }
    return new String(arr);
}

Sita's Stack Wisdom

Push all characters onto a stack. Pop them all — LIFO ensures reverse order. Append each popped character to build the reversed string.

java

String reverse(String s) {
    Stack<Character> stack = new Stack<>();
    // Push all characters
    for (char c : s.toCharArray()) stack.push(c);
    // Pop in reverse order
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.toString();
}

Step-by-Step Walkthrough

s="ab"
Push 'a': [a]
Push 'b': [a,b]
Pop 'b': sb="b"
Pop 'a': sb="ba"
Return "ba" ✅

Deep Insight

**The LIFO property:** Last pushed = first popped. This naturally reverses any sequence.

**Applications of stack reversal:** - Reversing strings/arrays (as here) - Evaluating postfix expressions in reverse - Undo operations (most recent action reversed first) - Browser back button (most recently visited page first) - Recursive call stacks (DFS, which is inherently reversible via explicit stack)

**This problem is a teaching tool.** In production code, `new StringBuilder(s).reverse().toString()` is preferred. But understanding that the stack reverses order is essential for st-4 (monotonic stack), st-5 (daily temperatures), and all complex stack problems.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	Char array + two-pointer swap
Optimal	O(n)	O(n)	Stack stores all chars before popping

Pattern Recognition

✅ Stack LIFO naturally reverses order
✅ Push all → pop all = reversed sequence
✅ Foundation for understanding monotonic stacks
✅ Teaching problem for stack mechanics

**LeetCode Trigger Phrases:**
→ Any reversal problem — consider stack
→ "LIFO" or "last in first out" behavior needed
→ Foundation for DFS, undo, and expression evaluation

Bhagavad Gita 13.12

अनादिमत्परं ब्रह्म न सत्तन्नासदुच्यते। सर्वतः पाणिपादं तत्सर्वतोऽक्षिशिरोमुखम्॥

The Supreme Brahman is without beginning and end, beyond existence and non-existence, with hands and feet everywhere, with eyes, heads, and faces everywhere.

Connection: The stack's LIFO mirrors a fundamental cosmic principle: what is last to enter the physical realm is first to return to the source. The string reversal through a stack is a meditation on this: the final letters of a word (last pushed) are closest to the source of meaning (first recalled). Every sequence, when properly stored and released, reveals its hidden reverse — the mirror truth within.