345. Reverse Vowels of a String

Description

The problem requires reversing only the vowels in a given string while keeping the positions of other characters unchanged. Vowels are defined as 'A', 'E', 'I', 'O', 'U' (both uppercase and lowercase).

Intuition

To solve this problem, we can first identify all the vowels in the string, reverse their order, and then insert them back into their original positions. By iterating over the string twice, once to collect the vowels and another to replace them, we can achieve the desired result.

Approach

1. Identify Vowels: First, iterate through the string and collect all the vowels in the order they appear.
2. Reverse Vowels: Reverse the list of vowels collected.
3. Replace Vowels: Iterate through the string again, replacing the original vowels with the reversed ones.
4. Return Result: The final string will have the vowels in reverse order while all other characters remain in their original positions.

Complexity

Time Complexity:

O(n), where n is the length of the string. The string is iterated over twice: once to collect vowels and once to replace them.

Space Complexity:

O(n) for storing the list of vowels.

Code

C++

class Solution {
public:
    std::string reverseVowels(std::string s) {
        std::string vowels = "AEIOUaeiou";
        std::string vow = "";
        for (char c : s) {
            if (vowels.find(c) != std::string::npos) {
                vow += c;
            }
        }
        std::reverse(vow.begin(), vow.end());
        int i = 0;
        for (char& c : s) {
            if (vowels.find(c) != std::string::npos) {
                c = vow[i++];
            }
        }
        return s;
    }
};

Python

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = "AEIOUaeiou"
        vow = [c for c in s if c in vowels]
        revStr = []
        i = 0
        for char in s:
            if char in vowels:
                revStr.append(vow.pop())
            else:
                revStr.append(char)
        return ''.join(revStr)

Java

class Solution {
    public String reverseVowels(String s) {
        String vowels = "AEIOUaeiou";
        StringBuilder vow = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                vow.append(c);
            }
        }
        vow.reverse();
        StringBuilder revStr = new StringBuilder();
        int i = 0;
        for (char c : s.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                revStr.append(vow.charAt(i++));
            } else {
                revStr.append(c);
            }
        }
        return revStr.toString();
    }
}

JavaScript

var reverseVowels = function (s) {
    let revStr = '', vowels = 'AEIOUaeiou', vow = '', i = 0

    for (let char of s) {
        if (vowels.includes(char)) {
            vow += char
        }
    }
    vow = vow.split('').reverse().join('')
    for (let char of s) {
        if (vowels.includes(char)) {
            revStr += vow[i]
            i++
        } else {
            revStr += char
        }
    }
    return revStr

};