Reverse a String

Problem Statement

Given a string, reverse it and return the reversed string.

Example:

• Input: "hello"

• Output: "olleh"

• Input: "OpenAI"

• Output: "IAnepO"

Approach 1: Brute Force (Using Extra String)

Intuition

Create a new string and build it by appending characters from the original string in reverse order.

Algorithm

1. Create an empty result string
2. Traverse the original string from end to start
3. Append each character to the result string

public class Solution {
    public String reverseString(String s) {
        StringBuilder reversed = new StringBuilder();
        
        for (int i = s.length() - 1; i >= 0; i--) {
            reversed.append(s.charAt(i));
        }
        
        return reversed.toString();
    }
}

Complexity Analysis

• Time Complexity: O(n) - Single pass through the string
• Space Complexity: O(n) - Extra string of size n

Approach 2: Optimal (Two Pointer - In Place)

Intuition

Use two pointers, one at the start and one at the end. Swap characters and move pointers towards each other. This works for mutable character arrays.

Algorithm

1. Convert string to character array (if needed)
2. Initialize left = 0 and right = n - 1
3. While left < right:
   • Swap characters at left and right
   • Increment left, decrement right

public class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while (left < right) {
            // Swap characters
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
    
    // Using StringBuilder
    public String reverseStringBuilder(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

Complexity Analysis

• Time Complexity: O(n) - We traverse n/2 elements
• Space Complexity: O(1) - In-place reversal (for mutable data structures)

Approach 3: Recursive

Intuition

Recursively reverse the substring and build the result.

public class Solution {
    public String reverseStringRecursive(String s) {
        if (s.length() <= 1) {
            return s;
        }
        return reverseStringRecursive(s.substring(1)) + s.charAt(0);
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Due to string concatenation in each recursive call
• Space Complexity: O(n) - Recursion stack depth

Key Takeaways

1. Two-pointer technique is efficient for in-place string reversal
2. In languages where strings are immutable (Java, Python), convert to char array first for O(1) space
3. The recursive approach is elegant but has higher time complexity due to string operations
4. Built-in methods like reverse() or [::-1] are optimized and preferred in production code