# Reverse Vowels of a String

March 24, 2020

I’m trying to get in a habit of starting my mornings off with coffee and a Leetcode problem before work. Ease my way into the day and get the brain juices flowing. Let’s jump in!

## Reverse Vowels of a String

### Problem

Write a function that takes a string as input and reverse only the vowels of a string.

The vowels does not include the letter `"y"`.

Example inputs:

``````Input: "hello"
Output: "holle"

Input: "leetcode"
Output: "leotcede"
``````

### Thinking

Initial thought was a queue as the data structure to use here. However, stack is what I wanted, I was just tired and messed up my ordering.

I spent some more time thinking about this and it can be solved with a double pointer iteration as well. This is likely the optimal implementation as it does not require double iteration, `O(2n)`.

Iterate over the string once, storing all vowels in the stack.

Iterate over it again to build the result string, use consonants when you find them. When you find a vowel, pop from the stack instead and continue.

### Corner Cases

The following corner cases are what I missed in my initial solution:

• I forgot to include capital letters in my frozenset for determine vowel vs. consonant. :facepalm:

### Improvements

As mentioned above, a double pointer (head/tail) iteration would be faster and use less memory.

### Solution

``````class Solution:
vowel_chars = frozenset(['a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U'])

def __init__(self):
self.vowels = []

def is_vowel(self, c):
return c in self.vowel_chars

def is_consonant(self, c):
return not self.is_vowel(c)

def reverseVowels(self, s: str) -> str:
result = ''

for c in s:
if self.is_vowel(c):
self.vowels.append(c)
else:
continue

for c in s:
if self.is_vowel(c):
result += self.vowels.pop()
else:
result += c

return result
``````

### Score

``````Runtime: 84 ms, faster than 16.99% of Python3 online submissions for Reverse Vowels of a String.
Memory Usage: 14.1 MB, less than 93.33% of Python3 online submissions for Reverse Vowels of a String.
``````

Return home