Problem Statement

Given a string, reverse the string using a stack data structure.

Input: A single string s containing only printable ASCII characters.

Output: A new string that is the reverse of the input string s.

Examples

Example 1:

Input: "hello"
Output: "olleh"

Example 2:

Input: "abcdefghi"
Output: "ihgfedcba"

Approaches

We can solve it using various ways, however in problem statement we are told to solve it using only the stack data structure.

1️⃣ Using a Stack: Iterative

Intuition:

A stack is a data structure that follows the Last-In-First-Out (LIFO) principle. When we push characters of the string onto the stack and then pop them off, the characters are reversed in order due to the LIFO property. This makes the stack a natural choice for this problem.

Steps:

1. Initialize a Stack: Create an empty stack to hold characters.
2. Push Characters: Traverse the string and push each character onto the stack.
3. Pop Characters: Pop each character from the stack and append it to a result string.
4. Return the Result: The result string will be the reversed version of the input string.

Code:

#include <iostream>
#include <stack>
#include <string>

std::string reverseString(const std::string& input) {
    std::stack<char> stack;
    
    // Push each character of the string onto the stack
    for (char ch : input) {
        stack.push(ch);
    }

    std::string reversedString;
    
    // Pop each character from the stack and append it to the result
    while (!stack.empty()) {
        reversedString += stack.top();
        stack.pop();
    }

    return reversedString;
}

int main() {
    std::string input;
    std::cout << "Enter a string to reverse: ";
    std::cin >> input;

    std::string reversed = reverseString(input);
    std::cout << "Reversed string: " << reversed << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string. Each character is pushed onto the stack and then popped off, both operations being O(1).
  • O(n) + O(n) ~ O(n)
    • One for traversal other for popping.
• Space Complexity: O(n), because the stack stores all n characters of the input string.

2️⃣ Using a Stack: Recursive

Intuition:

Instead of creating new substrings, we use an index to keep track of the current character in the string. The recursion progresses by moving this index forward. Once the end of the string is reached, the function starts appending characters in reverse order as the recursive calls unwind.

Code:

#include <iostream>
#include <string>

// Recursive function to reverse a string
void reverseString(const std::string& str, int index, int size, std::string& result) {
    // Base case: if the index reaches the size of the string, return
    if (index == size) {
        return;
    }

    // Recursive call with the next index
    reverseString(str, index + 1, size, result);

    // Append the current character after returning from the recursive call
    result += str[index];
}

int main() {
    std::string input = "abcdefghi";

    std::string reversed;
    reverseString(input, 0, input.size(), reversed);

    std::cout << "Reversed string: " << reversed << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string. Each character is processed exactly once.
• Space Complexity: O(n), due to the recursion call stack. There will be n recursive calls, each adding a frame to the stack.

3️⃣ Using Two-Pointer Technique

Intuition:

Instead of using extra space, we can use the two-pointer technique. One pointer starts at the beginning of the string, and the other starts at the end. By swapping the characters at these two pointers and moving the pointers towards each other, we can reverse the string in place.

Steps:

1. Initialize Two Pointers: Start with one pointer (left) at the beginning and the other (right) at the end of the string.
2. Swap Characters: Swap the characters at left and right.
3. Move Pointers: Increment left and decrement right.
4. Repeat: Continue until left is no longer less than right.

Code:

#include <iostream>
#include <string>

std::string reverseString(std::string input) {
    int left = 0;
    int right = input.length() - 1;

    while (left < right) {
        std::swap(input[left], input[right]);
        left++;
        right--;
    }

    return input;
}

int main() {
    std::string input;
    std::cout << "Enter a string to reverse: ";
    std::cin >> input;

    std::string reversed = reverseString(input);
    std::cout << "Reversed string: " << reversed << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string. Each character is swapped at most once.
• Space Complexity: O(1), as the reversal is done in place without using additional memory for another data structure.

4️⃣ Using Built-In Reverse Function

Intuition:

Most programming languages, including C++, provide a built-in function to reverse a container, such as a string or an array. Using the built-in function is the simplest and most efficient way if you do not have constraints on using standard library functions.

Steps:

1. Use the std::reverse function from the <algorithm> header to reverse the string directly.

Code:

#include <iostream>
#include <string>
#include <algorithm>

std::string reverseString(std::string input) {
    std::reverse(input.begin(), input.end());
    return input;
}

int main() {
    std::string input;
    std::cout << "Enter a string to reverse: ";
    std::cin >> input;

    std::string reversed = reverseString(input);
    std::cout << "Reversed string: " << reversed << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string.
• Space Complexity: O(1), since the reversal is performed in place.