easy Problem 2 Reverse a String

Problem Statement

Given a string, write a function that uses a stack to reverse the string. The function should return the reversed string.

Examples

Example 1:

Input: "Hello, World!"
Output: "!dlroW ,olleH"

Example 2:

Input: "OpenAI"
Output: "IAnepO"

Example 3:

Input: "Stacks are fun!"
Output: "!nuf era skcatS"

Constraints:

• 1 <= s.length <= 10⁵
• s[i] is a printable ascii character.

Solution

The solution to reverse a string can be elegantly achieved using a stack. The algorithm involves pushing each character of the string onto a stack and then popping them off, which naturally reverses their order. As we iterate through the string, each character is added to the top of the stack.

Once the entire string has been processed, we remove the characters from the stack one by one and append them to a new string. This process ensures that the characters are appended in reverse order, as the last character pushed onto the stack will be the first to be popped off. This method efficiently reverses the string while maintaining the integrity of the original data.

Here is the step-by-step algorithm.

1. Initialize an empty stack.
2. For each character in the input string, push the character into the stack.
3. Initialize an empty list reversedList to hold the string characters in the reversed order.
4. While the stack is not empty, pop out the top character from the stack and append it to the reversedList list.
5. Convert List of characters to the string.
6. Finally, return the reversed string.

Code

Here is how we can implement this algorithm:

import java.util.*;

public class Solution {

  // Function to reverse a given string using a stack
  public String reverseString(String s) {
    // Create a stack to store characters
    Stack<Character> stack = new Stack<>();

    // Push each character from the input string onto the stack
    for (char c : s.toCharArray()) {
      stack.push(c);
    }

    // Use a list to collect reversed characters
    List<Character> reversedList = new ArrayList<>(s.length());

    // Pop characters from the stack and add them to the list
    while (!stack.isEmpty()) {
      reversedList.add(stack.pop());
    }

    // Convert list to a string
    StringBuilder result = new StringBuilder(reversedList.size());
    for (char c : reversedList) {
      result.append(c);
    }

    return result.toString();
  }

  // Main method to test the reverseString function
  public static void main(String[] args) {
    Solution rs = new Solution();

    // Test cases
    System.out.println(rs.reverseString("Hello, World!")); // Output: "!dlroW ,olleH"
    System.out.println(rs.reverseString("OpenAI")); // Output: "IAnepO"
    System.out.println(rs.reverseString("Stacks are fun!")); // Output: "!nuf era skcatS"
  }
}

Complexity Analysis

Time Complexity

• Pushing characters onto the stack: The algorithm iterates through the input string and pushes each character onto the stack. This takes time, where N is the length of the input string.

• Popping characters from the stack: The algorithm then pops each character from the stack and appends it to a list (or an equivalent structure). This also takes time, as each character is processed once.

• Converting the list to a string: The final step is converting the list into a string. In most languages, this operation is since the list is iterated once.

• Final Complexity Calculation:

  • Pushing to the stack:
  • Popping from the stack:
  • Constructing the final string:

  Overall time complexity: .

Space Complexity

• Stack space: The stack stores all N characters from the input string, requiring space.

• List (or equivalent structure): The reversed characters are collected in a list (or similar structure), which also takes space.

• Final String Storage: The final reversed string takes space.

• Other Variables: We use a few auxiliary variables (char, int, etc.), but their space usage is , which is negligible.

• Final Complexity Calculation:

  • Stack storage:
  • List storage: *
  • Final string storage:

  Overall space complexity: .