The Indian Engineer

Problem 344 Reverse String

Posted on 2 mins

Two-Pointer String

Table of Contents

Problem Statement

Link - Problem 344

Question

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 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

Solution 

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

Complexity Analysis

Explanation

1. Intuition 

- Use two pointer approach to swap the elements.
- We need to write a swapping logic without using any extra space.

2. Implementation 

1. Initialize two pointers `start` and `end` to `0` and `s.size()-1` respectively.
2. Swap the elements at `start` and `end` index.
3. Increment `start` and decrement `end` until `start` is less than `end`.

Alternate Solution 

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(),s.end());
    }
};

Complexity Analysis

Explanation 

- This solution uses the inbuilt `reverse` function to reverse the string.

Utilizes the two pointer approach to swap the elements in the array.