Solution: Reverse a String

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Reverse a String

Table of Contents

Contents are not accessible

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<sup>5</sup>
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.

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

1 of 13

Code

Here is how we can implement this algorithm:

Python3

. . . .

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 $O(N)$ 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 $O(N)$ 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 $O(N)$ since the list is iterated once.
Final Complexity Calculation:
- Pushing to the stack: $O(N)$
- Popping from the stack: $O(N)$
- Constructing the final string: $O(N)$
Overall time complexity: $O(N) + O(N) + O(N) = O(N)$ .

Space Complexity

Stack space: The stack stores all N characters from the input string, requiring $O(N)$ space.
List (or equivalent structure): The reversed characters are collected in a list (or similar structure), which also takes $O(N)$ space.
Final String Storage: The final reversed string takes $O(N)$ space.
Other Variables: We use a few auxiliary variables (char, int, etc.), but their space usage is $O(1)$ , which is negligible.
Final Complexity Calculation:
- Stack storage: $O(N)$
- List storage: * $O(N)$
- Final string storage: $O(N)$
Overall space complexity: $O(N) + O(N) + O(N) = O(N)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible