Amazon Prime




 
Tagged
  • DSA Problems
  • String
  • Stack
  •  

    String Reverse Problem

    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

        StringReverse – Step 2

    • Step 3 :

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

        StringReverse – Step 3

    • 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 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

    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

    String Reverse - Two Pointer Technique

    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

    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
  •  
    ...