Kevin’s stack problem

Easy

0/40

Average time to solve is 20m

13 upvotes

Asked in companies

Problem statement

Kevin has recently learned the concept of “STACK”. During his practice, he got stuck in a problem where he has to reverse a string ‘S’ using a stack. So, he appoints you to help him in reversing the string ‘S’. All you have to do is to find the reversed string.

Please reverse the string using a stack so that Kevin gets to know where he is getting wrong after seeing your solution. It is guaranteed that strings will only be composed of English alphabets.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a string ‘S’.

Output Format:

For each test case, return the reversed string.

Output for every test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= |S| <= 10^4

Time limit: 1 sec

Sample Input 1:

2
CODINGNINJAS
WelcomeToCodeStudio

Sample Output 1:

SAJNINGNIDOC
oidutSedoCoTemocleW

Explanation of sample input 1:

In the first test case, the reverse of the given string is “SAJNINGNIDOC”.

In the second test case, the reverse of the given string is “oidutSedoCoTemocleW”.

Sample Input 2:

3
A
Aa
aA

Sample Output 2:

A
aA
Aa

Explanation for sample input 2:

In the first test case, the reverse of the given string is “A”.

In the second test case, the reverse of the given string is “aA”.

In the third test case, the reverse of the given string is “Aa”.

Hint 1

Put each character in the stack and then remove one by one.

Approaches (1)

Approach 1

Using a Stack

The basic idea is to push the whole string into a stack (character by character) and then take off each character from the stack one by one. The steps are as follows:

Iterate through ‘S’.
- Push each character into the stack.
Keep removing the top character from the stack until the stack becomes empty. Append each drawn character to the new string.
Return the new string.

Time Complexity

O(N), where ‘N’ is the length of the given string ‘S’.

Since we are iterating through the string once, so the time complexity will be O(N). Push and pop functions take constant time in the case of the stack. Thus, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the length of the given string ‘S’.

We are using a stack to store each string’s character, so the space complexity is O(N).

(100% EXP penalty)

Kevin’s stack problem

Console