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

1import java.util.Stack;
2
3public class StringReverseUsingStack {
4
5    // method to reverse given input string
6    public String reverse(String input){
7        if(input == null){
8            return null;
9        }
10        // Initialize stack and output array
11        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 stack
15        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 array
21        while (!stack.isEmpty()){
22            Character ch = stack.pop();
23            output[i++] = ch;
24        }
25
26        // convert the output array into string and return the result
27        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

Prerequisite

• Two Pointer Technique

Algorithm

1Input : A String
2
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 j
6
7Step 3: Move i pointer one step ahead and j pointer one step behind
8
9Step 4: Repeat step 1 until both i and j crosses with each other
10
11Step 5: Convert array into string and return
12

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 index
12        int i = 0;
13        int j = input.length-1;
14
15        // swap elements at 1 and j with each other
16        // move start pointer i with one step ahead 
17        // and j with one step behind
18        // continue same process until 
19        // both i and j crosses with each other
20        while (i<j) {
21            swap(input, i, j);
22            i++;
23            j--;
24        }
25        return String.valueOf(input);
26    }
27
28    // method to swap elements
29    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 Code
36    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