Problem Statement

Given an input string as an array of characters, write a function that reverses the string.

Examples

Example 1:
Input: String = “hello”
Output: Reverse of the string  = “olleh”

Example 2
Input : s = ["b", "y", "e" ]
Output : ["e", "y", "b"]

Explanation : The given string is s = "bye" and after reversing it becomes s = "eyb".

Constraints

1 <= s.length <= 103
s consist of only lowercase and uppercase English characters.

Approach

Theory

To print the reverse of a string using recursion, we can follow these steps:

1. Base Case: If the length of the string is 0, return.
2. Recursive Step: Print the last character of the string.
3. Recursive Call: Call the function recursively with the substring excluding the last character.

Approach

printReverse("hello")
                |
                | print 'o'
                | 
printReverse("hell")
                |
                | print 'l'
                | 
printReverse("hel")
                |
                | print 'l'
                | 
printReverse("he")
                |
                | print 'e'
                | 
printReverse("h")
                |
                | print 'h'

Code Implementation in C++:

#include <iostream>
#include <string>
using namespace std;

// Function to print reverse of a string using recursion
void printReverse(string str) {
    // Base case: if the length of the string is 0, return
    if (str.length() == 0)
        return;
    
    // Recursive step: print the last character of the string
    cout << str[str.length() - 1];

    // Recursive call: call the function recursively with the substring excluding the last character
    printReverse(str.substr(0, str.length() - 1));
}

int main() {
    string str = "hello";

    cout << "Reverse of the string \"" << str << "\" is ";
    printReverse(str);

    return 0;
}

Output:

Reverse of the string "hello" is olleh

Complexity Analysis:

• Time Complexity:O(n)
  • Since each character of the string is printed once.
• Space Complexity:O(n)
  • Due to the recursion stack, which can go as deep as the length of the string.

Another Way

Intuition:

Reversing a string through recursion involves conceptualizing the problem in smaller segments. The process identifies a base case where the left index surpasses or equals the right index, signaling completion. Characters at the left and right indices are swapped, and a recursive call is initiated with updated indices (left incremented, right decremented). This sequence of swaps ensures the entire string is reversed.

Approach

1. Identify the Base Case: Determine the condition under which the recursion should stop. For reversing a string, the recursion stops when the left index is greater than or equal to the right index. This indicates that we have reached the middle of the string and all necessary character swaps have been made.
2. Swap Characters at Indices: Perform the swap operation between the characters at the current left and right indices. This action exchanges the characters at the ends of the string segment being processed, which moves towards reversing the string.
3. Make Recursive Calls: After swapping, call the recursive function again with updated indices: increment the left index and decrement the right index. This step processes the next pair of characters moving inward until the base case is met.

Code in C++:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Recursive function to reverse the 
    string character by character */
    void reverse(vector<char>& s, int left, int right) {
        
        // Base case
        if (left >= right) return;
        
        // Swap characters at left and right positions
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        // Recursive call with updated indices
        reverse(s, left + 1, right - 1);
    }
    
public:
    // Function to reverse the given string
    vector<char> reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        reverse(s, left, right);
        return s;
    }
};

// Main function to test the solution
int main() {
    Solution solution;
    vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    
    // Function call to reverse the given string
    vector<char> reversed = solution.reverseString(s);
    for (char c : reversed) {
        cout << c << " ";
    }
    return 0;
}

OR:

#include <iostream>
#include <string>

using namespace std;

// Function to reverse a string using recursion
void reverse(string& str, int left, int right) {
    // Base case: Stop recursion when the two pointers meet or cross
    if (left >= right) {
        return;
    }

    // Swap characters at the current left and right positions
    swap(str[left], str[right]);

    // Recursive call: Move the left pointer forward and the right pointer backward
    reverse(str, left + 1, right - 1);
}

int main() {
    string str = "abc"; // Input string
    reverse(str, 0, str.length() - 1); // Call the reverse function
    cout << str; // Output the reversed string
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) - Each character in the string is processed exactly once, resulting in a linear time complexity relative to the length of the string.
• Space Complexity: O(N) - This is due to the recursion stack used in the process. In the worst case, the depth of the recursion is equal to the length of the string, leading to linear space complexity