Reversing a String with Constant Space Complexity in C++

Overview

Reversing a string in C++ while maintaining constant space complexity is a straightforward task. The key requirement is that the algorithm’s memory usage remains unchanged, regardless of the input string’s length. Whether the string contains a single character or thousands, the space allocated does not increase in accordance with the size of the string. This efficiency is achieved by modifying the string elements directly, performing all operations in place.

Approach

The most effective method for this task is the two-pointer technique. This approach is widely recognized for its efficiency in solving algorithmic problems and typically provides linear time complexity—a significant improvement over methods that use nested loops and result in quadratic time complexity. The two-pointer strategy uses two variables to track positions within the string, allowing elements to be swapped directly without allocating additional space in proportion to the input string.

Implementation

In practice, the left pointer is initialized at the start of the array, while the right pointer is set at the end. These pointers reference their respective index positions in the array. The core condition for iteration is that the left pointer remains less than the right pointer, ensuring that swaps occur only between distinct elements. During each iteration, a temporary variable is declared and initialized to store the value of the left element, facilitating a safe swap without data loss. After swapping, the left pointer is incremented and the right pointer is decremented, guiding both pointers toward the center of the array. It is crucial to assign the value to the right element from the temporary variable only after the left element has taken its new value.

It is important to note that you can use the built in C++ reverse function in the standard namespace that basically does the same thing. If you wish to use this convenient function all you must do is directly include the algorithm header or indirectly include it via other headers. The time complexity and space complexity are the same as my implementation.

void reverseString(std::string& s)
{
    size_t left = 0, right = s.size() - 1;

    while (left < right)
    {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        left++;
        right--;
    }
}

void reverseStringSTL(std::string& s)
{
    std::reverse(s.begin(), s.end());
}