Tagged
• DSA Problems
• String
• Stack
•

# Problem Statement

`1Problem Description : 2Given a String, return the reverse of the String. 3 4Input:  A String 5 6Output: Return reverse of the given string `

```1Example 1 :2
3  Input : Strive 4  Output: evirtS 5  Explanation : evirtS is reverse of Strive ```

```1Example 2 :2
3  Input : RENNIW 4  Output: WINNER 5  Explanation : WINNER is reverse of the string RENNIW```

# Solution Approaches

String reverse can be done using multiple approaches and below are the list of approaches for the given problem.

# Using Stack Data Structure

## Algorithm

```1Input : A String  2
3Step 1: Initialize a Stack, a char array (output) of length of size n  (where n is length of the given string)  4
5Step 2: Push all characters of the given string one by one 6
7Step 3: Pop letters from stack and put into output array starting with 0 index 8
9Step 4: convert output array into string and return ```

## Example Dry Run

Input String : RENNIW

• Step 1 :

• Create a Stack
• Create empty char array output
• Step 2 :

• push all characters of the string into stack one by one

• Step 3 :

• pop characters from stack one by one and put into output array

• Step 4 :

• convert output array into a string and return

Output String : WINNER

## Code Implementation

1. Java
2. Python

```1import java.util.Stack;2
3public class StringReverseUsingStack {4
5    // method to reverse given input string6    public String reverse(String input){7        if(input == null){8            return null;9        }10        // Initialize stack and output array11        Stack<Character> stack = new Stack<>();12        char[] output = new char[input.length()];13
14        // push letters of the given string one by one into the stack15        for(int i=0; i<input.length(); i++){16            stack.push(input.charAt(i));17        }18
19        int i = 0;20        // pop letters from stack one by one and put into output array21        while (!stack.isEmpty()){22            Character ch = stack.pop();23            output[i++] = ch;24        }25
26        // convert the output array into string and return the result27        return String.valueOf(output);28    }29
30    public static void main(String[] args){31        StringReverseUsingStack obj = new StringReverseUsingStack();32
33        // Example 1 :34        String input1 = "Strive" ;35        System.out.println(obj.reverse(input1));36
37        // Example 2:38        String input2 = "RENNIW" ;39        System.out.println(obj.reverse(input2));40    }41}```

## Complexity Analysis

• Time Complexity : O(n) where n is the length of the string
• Space Complexity: O(n) as we are using stack data structure.

# Using Two Pointer Technique

## Algorithm

```1Input : A String2
3Step 1: Convert string into char array input and initialize two pointers i and j with 0 and n-1 (n is length of the array)4
5Step 2: Swap elements at place i and j6
7Step 3: Move i pointer one step ahead and j pointer one step behind8
9Step 4: Repeat step 1 until both i and j crosses with each other10
11Step 5: Convert array into string and return12
```

## Example Dry Run

Input String : RENNIW

• Step 1 :

• convert string to a char array named input.
• initialize i = 0 and j = n-1 (5 for this example)
• Step 2:

• swap input[i] and input[j]
• Step 3:

• increment i with 1 and decrement j with 1 (i becomes i+1, j becomes j-1)
• Step 4:

• repeat from step 1 and it gets terminated when i = 3 and j = 2.
• Step 5:

• convert the final array into string and return the same.

Output String : WINNER

## Java Implementation

```1public class StringReverseUsingTwoPointerTechnique {2
3    public String reverse(String input) {4        if(input == null){5            return null;6        }7        return reverse(input.toCharArray());8    }9
10    private String reverse(char[] input) {11        // initialize i to 0 and j to last index12        int i = 0;13        int j = input.length-1;14
15        // swap elements at 1 and j with each other16        // move start pointer i with one step ahead 17        // and j with one step behind18        // continue same process until 19        // both i and j crosses with each other20        while (i<j) {21            swap(input, i, j);22            i++;23            j--;24        }25        return String.valueOf(input);26    }27
28    // method to swap elements29    private void swap(char[] input, int i, int j) {30        char temp = input[i];31        input[i] = input[j];32        input[j] = temp;33    }34
35    // Driver Code36    public static void main(String[] args) {37        StringReverseUsingTwoPointerTechnique obj = 38        new StringReverseUsingTwoPointerTechnique();39
40        // Example 1 :41        String input1 = "Strive" ;42        System.out.println(obj.reverse(input1));43
44        // Example 2:45        String input2 = "RENNIW" ;46        System.out.println(obj.reverse(input2));47    }48}```

## Complexity Analysis

• Time Complexity : O(n)
• Space Complexity: O(1)

# Approaches Comparison

ApproachTime ComplexitySpace ComplexityRemarks
Using StackO(n)O(n)Extra Space is needed
Using Two Pointer TechniqueO(n)O(1)No Extra Space

• DSA Problems
• String
• Stack
•
...