Reverse String (C++, Java, and Python)

Problem Statement

Given a string S. The task is to reverse the string.

Examples:

Input: S = “FACE”
Output: ECAF
Explanation: Provided in image above

Input:  S = “SCALER”
Output: RELACS

Approach 1: Recursion – In Place

The idea is to use a recursive approach to solve the problem. Observe the below image to understand the approach:

Algorithm:

• Initialise a helper function, which consists of two pointers, left and right as arguments respectively.
• left is initialised to 0 and right to N – 1, where N is the length of the given string.
• If left < right, swap S[left] and S[right] and call the helper function of (left + 1, right + 1).
• left >= right, is the base case, hence terminate the loop.

C++ Code

void helper(string s, int left, int right) {
  if (left >= right) return;
  char tmp = s[left];
  s[left++] = s[right];
  s[right--] = tmp;
  helper(s, left, right);
}
 
void reverseString(string s) {
  helper(s, 0, s.length() - 1);
}

Java Code

 public void helper(char[] s, int left, int right) {
  if (left >= right) return;
  char tmp = s[left];
  s[left++] = s[right];
  s[right--] = tmp;
  helper(s, left, right);
}
 
public void reverseString(char[] s) {
  helper(s, 0, s.length - 1);
}

Python Code

def reverseString(self, s):
    def helper(left, right):
        if left < right:
            s[left], s[right] = s[right], s[left]
            helper(left + 1, right - 1)
 
    helper(0, len(s) - 1)

Time Complexity:O(N), where N is the length of the string.
Space Complexity:O(N), since the recursion stack takes space.

Approach 2: Two Pointers

Another simple approach to solve this problem is to use two pointers method. One of the pointers is set at the beginning of the string and another at the end. The process is continued, till both the pointers don’t coincide.

Algorithm:

• Set left = 0 and right = N – 1, where N is the length of the given string.
• While left < right:
  • Swap S[left] and S[right].
  • Move the left pointer forward and the right pointer backwards.
• Stop the algorithm, when left == right.

C++ Implementation

void reverseString(string &s) {
  int left = 0, right = s.length() - 1;
  while (left < right) {
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
  }
}

Java Implementation

 public void reverseString(char[] s) {
  int left = 0, right = s.length - 1;
  while (left < right) {
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
  }
}

Python Implementation

def reverseString(self, s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left, right = left + 1, right - 1

Time Complexity:O(N), where N is the length of the string.
Space Complexity:O(1), since no extra space is used.

Approach 3: Using in-built functions

Each programming language has some unique library functions that can perform some specific features.
In this section, we will talk about each of those one by one.

C++ code for the approach

In CPP, there is an inbuilt reverse function in the algorithm header file, which when accessed can reverse string/array.

void reverseString(string &s) {
  reverse(s.begin(), s.end());
}

Java code for the approach

In Java, builtin reverse function can be used by converting the given string to Stringbuilder. The string class doesn’t have a reverse function.

public void reverseString(String s) {
  StringBuilder res = new StringBuilder();
  res.append(s);
  res.reverse();
}

Python code for the approach

Similar to other languages, Python too has an inbuilt reverse function, which can be used to reverse a string.

def reverse(string):
    string = "".join(reversed(string))
    return string

Practice Question

Reverse The String

FAQs

Q.1: What is the space complexity of reversing a string using recursion?

Ans: The space complexity of reversing string using recursion is O(N) since the recursion stack takes space.

Q.2: Is there some other method to reverse the string?

Ans: Yes, the string can be reversed using many different methods. For example, the string can be reversed using a stack.