Reverse String in C++

Given a string, write a function that reverses that string without using built-in functions or libraries.

Example:

Input:  "hello"

Output: "olleh"

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

Understanding the Problem

The core challenge of this problem is to reverse a given string without using any built-in functions or libraries. This means we need to manually manipulate the string to achieve the desired result. Reversing a string is a common problem in computer science with applications in data processing, text manipulation, and more.

Potential pitfalls include handling empty strings and ensuring that the algorithm runs efficiently within the given constraints.

Approach

To solve this problem, we can use a two-pointer technique. This approach involves swapping characters from the beginning and end of the string, moving towards the center. This method ensures that we reverse the string in-place, achieving O(n) time complexity. However, since we need to use O(n) extra space, we will create a new string to store the reversed characters.

Naive Solution

A naive solution might involve iterating through the string and appending characters to a new string in reverse order. While this works, it is not optimal in terms of space complexity if we consider in-place reversal.

Optimized Solution

The optimized solution involves using a two-pointer technique:

Initialize two pointers, one at the beginning (left) and one at the end (right) of the string.
Swap the characters at these pointers and move the pointers towards the center.
Continue this process until the pointers meet or cross each other.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Create a new string of the same length as the input string to store the reversed characters.
Initialize two pointers, left at the start (0) and right at the end (length-1) of the string.
While left is less than or equal to right:
- Assign the character at the left pointer to the corresponding position in the new string from the end.
- Assign the character at the right pointer to the corresponding position in the new string from the start.
- Move the left pointer to the right and the right pointer to the left.
Return the new string.

Code Implementation

#include <iostream>
#include <string>

std::string reverseString(const std::string &str) {
    int n = str.length();
    std::string reversed(n, ' '); // Create a new string of the same length

    int left = 0;
    int right = n - 1;

    while (left <= right) {
        reversed[left] = str[right];
        reversed[right] = str[left];
        left++;
        right--;
    }

    return reversed;
}

int main() {
    std::string input = "hello";
    std::string output = reverseString(input);
    std::cout << "Reversed string: " << output << std::endl;
    return 0;
}

Complexity Analysis

The time complexity of this algorithm is O(n) because we iterate through the string once. The space complexity is also O(n) because we create a new string to store the reversed characters.

Edge Cases

Consider the following edge cases:

Empty string: The function should return an empty string.
Single character string: The function should return the same single character.
Strings with special characters and spaces: The function should correctly reverse all characters, including special characters and spaces.

Testing

To test the solution comprehensively, consider the following test cases:

Input: "hello" - Output: "olleh"
Input: "" - Output: ""
Input: "a" - Output: "a"
Input: "A man, a plan, a canal, Panama" - Output: "amanaP ,lanac a ,nalp a ,nam A"

Use a testing framework like Google Test for C++ to automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about different approaches and their trade-offs.
Write pseudocode to outline your solution before coding.
Test your solution with various edge cases to ensure robustness.

Conclusion

Reversing a string is a fundamental problem that helps in understanding string manipulation and algorithm design. By practicing such problems, you can improve your problem-solving skills and gain a deeper understanding of algorithmic concepts.

Additional Resources

For further reading and practice, consider the following resources:

Reverse String in O(n) Time and O(n) Space using C++