algoadvance

Leetcode 344. Reverse String

Problem Statement

The problem is to reverse a given string in place. The function should do this without using any extra space for another array (modifying the input array directly is required).

Leetcode Problem Number: 344

Given a character array s, reverse the array.

Example:

Input: ['h', 'e', 'l', 'l', 'o']
Output: ['o', 'l', 'l', 'e', 'h']

Clarifying Questions

  1. Input Type: Is the input guaranteed to be a character array?
    • Yes.
  2. In-place Requirement: Are we allowed to use extra space, such as another array, to store the result?
    • No, the array must be reversed in place.
  3. Input Size: Is there a constraint on the size of the input array?
    • No specific constraint, but generally expect it to be reasonably sized to fit in memory.
  4. Unicode Characters: Does the array contain only ASCII characters, or can it contain Unicode characters?
    • It can contain Unicode characters, but the operations would be the same as with ASCII.

Strategy

To reverse the string in place, we can use the two-pointer technique:

  1. Initialize two pointers: one (left) at the beginning of the array and the other (right) at the end of the array.
  2. Swap the elements at these two pointers.
  3. Move the left pointer one step to the right and the right pointer one step to the left.
  4. Repeat steps 2-3 until left is greater than or equal to right.

This approach ensures we process each character only once and swap them in place without using any extra space.

Time Complexity

Code

Here’s the Java implementation of the above strategy:

public class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

This code defines a class Solution with a method reverseString that takes a character array s as input and reverses it in place.

The while loop continues until the left pointer is no longer less than the right pointer, ensuring that we swap elements from the outside towards the center of the array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI