Reverse String

Problem Statement

The task is to create a function that reverses a given string. However, the string is not provided in its traditional form but as an array of characters denoted by s. The critical constraint to this problem is that the reversal must be done in-place. This means that no additional data structures can be used to hold intermediate results, which further implies that the space complexity must be (O(1)). Therefore, the solution must directly modify the array s without using extra space proportional to the length of the string.

Examples

Example 1

Input:

s = ["h","e","l","l","o"]

Output:

["o","l","l","e","h"]

Example 2

Input:

s = ["H","a","n","n","a","h"]

Output:

["h","a","n","n","a","H"]

Constraints

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

Approach and Intuition

The problem involves reversing an array of characters without using additional storage, adhering to (O(1)) space complexity. Here is a step-by-step explanation and the intuitive thought behind solving this problem:

1. Two-pointer Approach:

   • Utilize two pointers: one pointing at the beginning of the array (start) and the other at the end (end).

2. Swapping:

   • Swap the elements at the start and end pointers.
   • Increment the start pointer to move forward and decrement the end pointer to move backward.

3. Termination:

   • Continue the swapping until the start pointer is less than the end pointer. This condition ensures that all characters are reversed in their positions without re-swapping the already swapped elements.

Using this method ensures in-place modification of the array and adherence to the constraints provided:

• Constraint Validation:
  • The size constraint of 1 <= s.length <= 105 ensures the function can handle both small and very large strings efficiently.
  • The character constraint that s[i] must be a printable ASCII character simplifies consideration, avoiding complexities with non-standard characters or Unicode encodings.

This approach effectively uses the properties of array indices and direct element swapping, making it optimal for scenarios requiring low space usage.

Solutions

class Solution {
    public void reverseChars(char[] str) {
        int start = 0, end = str.length - 1;
        while (start < end) {
            char temp = str[start];
            str[start++] = str[end];
            str[end--] = temp;
        }
    }
}