Reverse String Without Temporary Variable

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

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.

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.