Reverse String Without Temporary Variable  

Difficulty Level Medium
Frequently asked in Adobe Amazon Google Hulu Microsoft Moonfrog Labs
Bitwise-XOR String

Problem Statement  

In the “Reverse String Without Temporary Variable” problem we have given a string “s”. Write a program to reverse this string without using any extra variable or space.

Input Format  

The first line containing the given string “s”.

Output Format  

Print the string which is reverse of the given string.

Constraints  

  • 1<=|s|<=10^6
  • s[i] must be a lower case alphabet

Example  

tutorialcup
puclairotut

Explanation: “puclairotut” is the reverse of the “tutorialcup”.

Please click Like if you loved this article?

Algorithm to Reverse String Without Temporary Variable  

1. Store start index in low and end index in high.

2. Here, without creating a temp variable to swap characters, we use xor(^).

3. Traverse the input string “s”.

4. Swap from first variable to end using xor.

  • Do xor s[high] with s[low] and store it into s[low].
  • Now, do xor of s[low] with s[high] and store it into s[high].
  • Now again, do xor s[high] with s[low] and store it into s[low].

5. Return the final output string.

Implementation  

C++ Program to Reverse String Without Temporary Variable

#include <bits/stdc++.h>
using namespace std;
int main()
{
   string s;
   cin>>s;
   int n=s.length();
   int start=0,end=n-1;
   while(start<end)
   {
       s[start]^=s[end];
       s[end]^=s[start];
       s[start]^=s[end];
       start++;
       end--;
   }
   cout<<s<<endl;
   return 0;
}

Java Program to Reverse String Without Temporary Variable

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                char a[] = s.toCharArray();
    int n = s.length();
                int start = 0, end=n-1;
                while(start<end)
                {
                    a[start]^=a[end];
                    a[end]^=a[start];
                    a[start]^=a[end];
                    end--;
                    start++;
                }
                for(int i=0;i<n;i++)
                System.out.print(a[i]);
                System.out.println();
  } 
} 
answer
rewsna

Complexity Analysis to Reverse String Without Temporary_Variable  

Time Complexity

O(n) where n is the size of the given string, Here we just traverse the given string and perform xor operation three times to swaps the values between two indexes.

See also
Prefix to Infix Conversion

Space Complexity

O(1) because we don’t use any auxiliary space at here. We perform the xor operator three times to swaps the values between the two indexes.

Please click Like if you loved this article?