LeetCode: Reverse Vowels of a String

Key takeaways:
The task is to reverse the positions of vowels in a string while keeping consonants unchanged.
Vowels include ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ (both cases).
The algorithm uses two pointers: leftIndex at the start and rightIndex at the end.
It finds and swaps the leftmost and rightmost vowels, moving the pointers inward.
This continues until the pointers cross each other.
Time complexity is O(n) for a single traversal; space complexity is O(1) due to a single temporary variable.

There’s this interesting puzzle when dealing with string manipulation where we’re supposed to switch the places of all the vowels in a given string. VowelsVowels are speech sounds represented by letter 'a', 'e', 'i', 'o', and 'u' are scattered throughout the string, and we want to flip their positions around. It’s a bit like playing with language, but it’s also something we might encounter in real-world tasks, like text processing or game development. We’ll dive into the problem and how to solve it, and even do a quiz to ensure we’re all on the same page. So let’s unravel this challenge together!

Algorithm

Below is the algorithm we’ll be using to tackle this problem:

Initialize two pointers, leftIndex pointing to the beginning of the string str, and rightIndex pointing to the end of the string.
While leftIndex is less than rightIndex, we traverse the string from both ends.
1. At each step, we look for the leftmost vowel (using isVowel function) starting from leftIndex and the rightmost vowel starting from rightIndex.
2. Once we find both vowels, we swap them in the string.
3. We increment leftIndex and decrement rightIndex to continue searching for vowels until the pointers cross each other.
4. We continue this process until leftIndex is no longer less than rightIndex, indicating that we have traversed the entire string.
Finally, we return the modified string with vowels reversed.

Let’s look at the following illustration to get a better understanding of the solution:

#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
    bool isVowel(char ch) {
        return ch == 'a' || ch == 'i' || ch == 'e' || ch == 'o' || ch == 'u'
            || ch == 'A' || ch == 'I' || ch == 'E' || ch == 'O' || ch == 'U';
    }
    
    string reverseVowels(string str) {
        int leftIndex = 0;
        int rightIndex  = str.size() - 1;
        
        while (leftIndex < rightIndex) {
            while (leftIndex < str.size() && !isVowel(str[leftIndex])) {
                leftIndex++;
            }
            while (rightIndex >= 0 && !isVowel(str[rightIndex])) {
                rightIndex--;
            }
            if (leftIndex < rightIndex) {
                swap(str[leftIndex++], str[rightIndex--]);
            }
        }
        
        return str;
    }
};
int main() {
    Solution sol;
    // Test cases
    string words[] = {"hello", "EducAtive", "apple", "programming", "Algorithms"};
    int len = sizeof(words) / sizeof(words[0]);
    for(int i = 0; i < len; ++i) {
        string reversedWord = sol.reverseVowels(words[i]);
        cout << i+1<< ". \tWord: " << words[i] << "\n " <<" \tVowels reversed: "<< reversedWord << endl;
        cout << "\n" << string(100, '-') << endl;
    
    }
    
    return 0;
}

Reverse vowels of a string

Code explanation

Line 7: The isVowel function checks if a given character is a vowel by comparing it with a predefined list of vowels, both lowercase and uppercase.
Line 12: We take the string in the reverseVowels function.
Line 13: We initialize leftIndex to 0, indicating the starting position of the string.
Line 14: We initialize rightIndex to str.size() - 1, indicating the ending position of the string.
Line 16: We enter a while loop that continues until leftIndex is less than rightIndex, ensuring we haven’t traversed the entire string.
Lines 17–18: Within the loop, we traverse the string from left to right, looking for the leftmost vowel. We use the isVowel function to check if the current character is a vowel.
Lines 20–21: Similarly, we traverse the string from right to left, searching for the rightmost vowel.
Line 23: If we find both a leftmost and a rightmost vowel, we swap their positions in the string using the swap function.
Line 24: We increment leftIndex and decrement rightIndex to continue searching for vowels until the pointers cross each other.
Line 28: Finally, we return the modified string with vowels reversed.

Complexity analysis

Let’s look at the time and space complexity of this solution:

Time complexity

The time complexity of this solution is linear, denoted as $O(n)$ , where N is the length of the string, because the pointers traverse the list once.

Space complexity

The space complexity of this solution is $O(1)$ as we only used a temporary variable for swapping purposes.

LeetCode: Reverse Vowels of a String

Problem statement

Knowledge test

Algorithm

Coding example

Code explanation

Complexity analysis