algoadvance

Leetcode 344. Reverse String

Problem Statement

Leetcode Problem “344. Reverse String”

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example:

Input: s = ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]

Clarifying Questions

  1. Input Constraints:
    • Will the input array always be non-empty?
    • Can we assume that the input array contains only printable ASCII characters?
  2. Output Constraints:
    • Should the function return the reversed array or just modify it in place?
  3. Edge Cases:
    • How should the function handle arrays with a single character or an array of all identical characters?

Assuming:

  1. The input array will always be non-empty.
  2. The input array contains only printable ASCII characters.
  3. The function just needs to reverse the array in place and doesn’t need to return the array itself.

Strategy

The problem requires reversing the string in place, thus the two-pointer technique will be effective here:

  1. Initialize two pointers - one at the beginning (left) and one at the end (right) of the array.
  2. Swap the characters at the left and right pointers.
  3. Move the left pointer towards the center of the array (increment it) and the right pointer towards the center of the array (decrement it).
  4. Repeat steps 2 and 3 until the left pointer is greater than or equal to the right pointer.

Time Complexity

The algorithm runs in O(N) time, where N is the number of characters in the string, because we are essentially swapping half the elements with the other half.

The space complexity is O(1) as we are not utilizing any extra data structures that grow with the input size.

Code

Here’s the implementation of the strategy in C++:

#include <vector>
#include <iostream>

class Solution {
public:
    void reverseString(std::vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        
        while(left < right) {
            std::swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

int main() {
    Solution solution;
    std::vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    
    std::cout << "Original string: ";
    for (char c : s) {
        std::cout << c;
    }
    std::cout << std::endl;
    
    solution.reverseString(s);
    
    std::cout << "Reversed string: ";
    for (char c : s) {
        std::cout << c;
    }
    std::cout << std::endl;
    
    return 0;
}

Explanation

  1. Initialization:
    • left is initialized to 0 (beginning of the array).
    • right is initialized to s.size() - 1 (end of the array).
  2. Loop Condition:
    • The loop runs until left is less than right.
  3. Swapping:
    • The characters at positions left and right are swapped.
  4. Pointer Movement:
    • The left pointer is incremented by one.
    • The right pointer is decremented by one.
  5. End of Loop:
    • The loop stops when left is no longer less than right, meaning the string has been reversed.

This code effectively reverses the input string in place with constant extra space, meeting the problem’s requirements.

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