algoadvance

Leetcode 345. Reverse Vowels of a String

Problem Statement

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Examples:

  1. Input: s = “hello” Output: “holle”

  2. Input: s = “leetcode” Output: “leotcede”

Clarifying Questions

  1. Q: Should the case of the characters be considered when identifying vowels? A: Yes, both uppercase and lowercase vowels should be reversed.

  2. Q: Can the input string contain non-alphabetic characters? A: Yes, the input string can contain any characters, but only vowels are to be reversed.

  3. Q: Are there constraints on the size of the input string? A: The string’s length is in a reasonably small range to avoid performance issues (like typical competitive programming constraints).

Strategy

  1. Use two pointers to traverse the string from both ends: the left pointer starts at the beginning, and the right pointer starts at the end.
  2. Move both pointers towards each other.
  3. If both pointers point to vowels, swap these vowels.
  4. Continue moving the pointers until they meet or cross each other.

This approach ensures that we minimally traverse through the string while identifying vowels and performing swaps.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string. This is because each character in the string is processed at most once.

Code

Here is the C++ implementation of the strategy:

#include <iostream>
#include <unordered_set>

class Solution {
public:
    std::string reverseVowels(std::string s) {
        std::unordered_set<char> vowels {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            // Move left pointer to the next vowel
            while (left < right && vowels.find(s[left]) == vowels.end()) {
                left++;
            }
            // Move right pointer to the previous vowel
            while (left < right && vowels.find(s[right]) == vowels.end()) {
                right--;
            }
            // Swap the vowels
            if (left < right) {
                std::swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

// Example usage
int main() {
    Solution solution;
    std::string input1 = "hello";
    std::string input2 = "leetcode";
    std::cout << "Reversed vowels (hello): " << solution.reverseVowels(input1) << std::endl;
    std::cout << "Reversed vowels (leetcode): " << solution.reverseVowels(input2) << std::endl;
    return 0;
}

This code defines a method reverseVowels in the Solution class, which takes a string as input and returns the string with its vowels reversed. The main function demonstrates how to use this method with example inputs.

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