Reverse a string

Intuition

To reverse a string, the stack data structure is particularly useful due to its Last-In-First-Out (LIFO) principle. The thought process involves pushing each character of the string onto the stack, which naturally reverses their order. When characters are then popped off the stack, they are retrieved in the reverse sequence from their original arrangement. This approach efficiently leverages the stack's properties to achieve the desired reversal of the string.

Approach

Create an empty stack to store characters. Iterate over the given string from the first character to the last.
During each iteration, push the current character onto the stack. After completing the iteration, initialize a while loop to extract characters from the stack.
In each iteration of the while loop, pop the top character from the stack and append it to a new string or directly modify the original string to reverse its content.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to reverse a string
    void reverseString(vector<char>& s) {
        stack<char> stack;
        
        // Push characters onto the stack
        for (char c : s) {
            stack.push(c);
        }
        
        // Pop characters from the stack to reverse the string
        for (int i = 0; i < s.size(); ++i) {
            s[i] = stack.top();
            stack.pop();
        }
        
        return;
    }
};

int main() {
    vector<char> str = {'h', 'e', 'l', 'l', 'o'};
    
    // Creating an instance of Solution class
    Solution sol;
    
    // Function call to reverse the string
    sol.reverseString(str);

    for (char c : str) {
        cout << c;
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to reverse the string 
    public void reverseString(Vector<Character> s) {
        Stack<Character> stack = new Stack<>();

        // Push characters onto the stack
        for (char c : s) {
            stack.push(c);
        }

        // Pop characters from the stack to reverse the string
        for (int i = 0; i < s.size(); ++i) {
            s.set(i, stack.pop());
        }

        return;
    }
}

class Main {
    public static void main(String[] args) {
        Vector<Character> str = 
            new Vector<>(Arrays.asList('h', 'e', 'l', 'l', 'o'));

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to reverse the string
        sol.reverseString(str);

        for (char c : str) {
            System.out.print(c);
        }
    }
}
class Solution:
    # Function to reverse a string
    def reverseString(self, s):
        stack = []

        # Push characters onto the stack
        for c in s:
            stack.append(c)

        # Pop characters from the stack to reverse the string
        for i in range(len(s)):
            s[i] = stack.pop()

        return

# Main function
if __name__ == "__main__":
    str_list = ['h', 'e', 'l', 'l', 'o']

    # Creating an instance of Solution class
    sol = Solution()

    # Function call to reverse the string
    sol.reverseString(str_list)

    print("".join(str_list))
class Solution {
    // Function to reverse a string
    reverseString(s) {
        const stack = [];

        // Push characters onto the stack
        for (let c of s) {
            stack.push(c);
        }

        // Pop characters from the stack to reverse the string
        for (let i = 0; i < s.length; ++i) {
            s[i] = stack.pop();
        }

        return;
    }
}

// Main function
const main = () => {
    const str = ['h', 'e', 'l', 'l', 'o'];

    // Creating an instance of Solution class
    const sol = new Solution();

    // Function call to reverse the string
    sol.reverseString(str);

    console.log(str.join(""));
};

main();

Complexity Analysis

Time Complexity O(N) - Linear time complexity, where N is the length of the string. The algorithm iterates over the string once to push characters onto the stack and then iterates again to pop characters from the stack.

Space Complexity O(N) - Linear space complexity. This is due to the usage of the extra data structure of stack, which grows linearly with the size of the input string.

Intuition

To reverse a string, another method is swapping the characters from the beginning and end simultaneously. This can be achieved using two pointers: one positioned at the leftmost character and the other at the rightmost character. Swap these two characters and then move both the pointers toward the center until they meet. In this manner, the first character is swapped with the last, the second with the second last, and so forth.

Approach

Set up two pointers: i and j.Initialize the pointer i to 0 (the start of the string) and j to (length of string - 1) (the end of the string).
Use a while loop to iterate as long as i is less than j and in each iteration, swap the characters at positions i and j.
After swapping, increment i by 1 and decrement j by 1. Continue this process until the pointers meet or cross each other.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to reverse a string
    void reverseString(vector<char>& s) {
        int start = 0, end = s.size()-1;
        
        // Until the string is reversed
        while(start < end) {
            // Swap the characters at start and end
            char ch = s[start];
            s[start] = s[end];
            s[end] = ch;
            
            // Move the pointers towards the center
            start++, end--;
        }
        
        return;
    }
};

int main() {
    vector<char> str = {'h', 'e', 'l', 'l', 'o'};
    
    // Creating an instance of Solution class
    Solution sol;
    
    // Function call to reverse the string
    sol.reverseString(str);

    for (char c : str) {
        cout << c;
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to reverse the string 
    public void reverseString(Vector<Character> s) {
        int start = 0, end = s.size() - 1;

        // Until the string is reversed
        while (start < end) {
            // Swap the characters at start and end
            char ch = s.get(start);
            s.set(start, s.get(end));
            s.set(end, ch);

            // Move the pointers towards the center
            start++;
            end--;
        }

        return;
    }
}

class Main {
    public static void main(String[] args) {
        Vector<Character> str = 
            new Vector<>(Arrays.asList('h', 'e', 'l', 'l', 'o'));

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to reverse the string
        sol.reverseString(str);

        for (char c : str) {
            System.out.print(c);
        }
    }
}
class Solution:
    # Function to reverse a string
    def reverseString(self, s):
        start, end = 0, len(s) - 1

        # Until the string is reversed
        while start < end:
            # Swap the characters at start and end
            s[start], s[end] = s[end], s[start]

            # Move the pointers towards the center
            start += 1
            end -= 1

        return

# Main function
if __name__ == "__main__":
    str_list = ['h', 'e', 'l', 'l', 'o']

    # Creating an instance of Solution class
    sol = Solution()

    # Function call to reverse the string
    sol.reverseString(str_list)

    print("".join(str_list))
class Solution {
    // Function to reverse a string
    reverseString(s) {
        let start = 0, end = s.length - 1;

        // Until the string is reversed
        while (start < end) {
            // Swap the characters at start and end
            const temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            // Move the pointers towards the center
            start++;
            end--;
        }

        return;
    }
}

// Main function
const main = () => {
    const str = ['h', 'e', 'l', 'l', 'o'];

    // Creating an instance of Solution class
    const sol = new Solution();

    // Function call to reverse the string
    sol.reverseString(str);

    console.log(str.join(""));
};

main();

Complexity Analysis

Time Complexity O(N) - Linear time complexity, where n is the length of the string. The algorithm iterates through half of the string.

SpaceComplexity O(1) - Constant space complexity. The algorithm only uses a few extra variables regardless of the input size.

Note: This same approach can also be implemented using recursion. Recursively, the function can swap the characters at the two ends of the string and then call itself for the substring excluding these ends until the string is reversed.

Problem List

Examples:

Constraints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Notes

Code