Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Reverse Vowels

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.

Example 1:

Input: s= "hello"
Output: "holle"

Example 2:

Input: s= "AEIOU"
Output: "UOIEA"

Example 3:

Input: s= "DesignGUrus"
Output: "DusUgnGires"

Constraints:

  • 1 <= s.length <= 3 * 10<sup>5</sup>
  • s consist of printable ASCII characters.

.....

.....

.....

Like the course? Get enrolled and start learning!
Nabeel Keblawi

Nabeel Keblawi

· 2 years ago

Alternative solution to two pointers is using a stack, which is a Last In First Out data structure. Since the last vowel in the original string will be the first vowel in the new string, I chose to use a stack. Here's how I did it:

class Solution:
  def reverseVowels(self, s: str) -> str:
    vowels = 'aeiouAEIOU'
		vowelStack = [] # Create an empty stack
		newString = ''

    for c in s:
      if c in vowels:
        vowelStack.append(c) # Push vowel onto stack
    
    for c in s:
      if c in vowels:
        newString += vowelStack.pop() # This is where vowels are reversed
      else: newString += c

    return newString
Show 1 reply
N

nikita michaelson

· 3 years ago

 
class Solution:   
def reverseVowels(self, s: str) -> str:     
  vowels = set(['A','a','E','e','i','I','O','o','U','u'])     
  order = [] # use a list as those are ordered     
  ans = ""     
  for x in s: # for all the letters in the string , if a vowel , store in a list       
   if x in vowels:         
    order.append(x)     
  for x in s: # build new string with the vowels reversed using pop function        
   if x in vowels:        
    ans += order.pop()        
   else:         
    ans +=x       
 return ans
Show 4 replies
Vini Neto

Vini Neto

· 2 years ago

class Solution:
  def reverseVowels(self, s: str) -> str:
    vowels = set('aeiouAEIOU')
    s_list = list(s)
    left, right = 0, len(s) -1
    while left < right:
      if s_list[left] not in vowels:
        left += 1
      elif s_list[right] not in vowels:
        right -= 1
      else:
        s_list[left], s_list[right] = s_list[right], s_list[left]
        left += 1
        right -= 1
    return ''.join(s_list)
V

Victor An

· 3 years ago

is self.vowels.find(array[first]) efficient?

I would better to use a hashset to replace it.

Show 1 reply
Dang Khoa Tran

Dang Khoa Tran

· 2 years ago

class Solution {
public:
    bool isVowels(char c) {
        c = tolower(c);
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
    }
    string reverseVowels(string s) {
        int i=0, j=s.length()-1;

        while (i<=j) {
            while(i<=j && !isVowels(s[i])) i++;
            while(i<=j && !isVowels(s[j]))j--;

            if (i<=j) {
                swap(s[i++], s[j--]);
            }
            
        }

        return s;
    }
};
Naveen Kumar

Naveen Kumar

· a year ago

Although provided solution works for all cases, it is not very obvious and one will need to run through corner cases to confirm that this solution actually works for all cases. Adding a start<end check before swapping makes it clearer and more obvious.

Luis Roel

Luis Roel

· 3 years ago

class Solution:
  def reverseVowels(self, s: str) -> str:
    # We need a way to do membership checks
    # and a set is a good way, since our reference
    # set isn't very large.
    vowels = set('aAeEiIoOuU')
    # Conver the string to a list so its easier to process
    s_list = [c for c in s]

    # Notice how the vowels switch sides?
    # hello -> holle, this tells me they're
    # processing the string from both ends
    # which means this is a good candidate for
    # two pointers
    l, r = 0, len(s) - 1

    # Non inclusive because you can't flip the middle
    # onto itself
    while l < r:
      # The problem doesn't seem to mention we'll be dealing
      # with spaces...so I don't think there's a need to check
      # This line checks whether each index in the strin
Show 1 reply
Ashutosh Tiwari

Ashutosh Tiwari

· 2 years ago

Where are you checking weather character is vowel or non vowel before increment first and decrementing last pointers .

I am not sure if this is the level of content quality design guru is providing, should i mentioned this on the public forum and spread the awareness among others about the content quality . I have paid very high amount to get this course

Dhruv Mohindru

Dhruv Mohindru

· 3 months ago

An alternative approach to two pointer technique where we don't need inner while loops

  1. Create an array from a string so that swapping of characters is easy
  2. Initialise left to index 0 of array
  3. Initialise right to array size - 1
  4. Run a while loop till left < right
  5. If both the character at index left and right are vowel (ignoring case), then swap them
  6. otherwise if character at index left in not vowel increment left by 1
  7. otherwise if character at index right in not vowel decrement right by 1
  8. when loop terminates we have a swapped charater array
  9. convert character array to string and return
// Solution in rust
fn reverse_vowels(input: String) -> String {
    /*
    Time Complexity: O(n)
    - Converting String to mutable Vec n = O(n)
    - While loop wil
Foued Benzaid

Foued Benzaid

· 2 months ago

Clean approach :

def reverseVowels(s: str) -> str:
  vowels = "aeiouAEIOU"
  mys = list(s)
  left = 0
  right = len(s) -1
  while left < right:
    while left < right and mys[left] not in vowels:
      left += 1
    while right > left and mys[right] not in vowels:
      right -= 1
    mys[left], mys[right] = mys[right], mys[left]

    left += 1
    right -= 1

  return "".join(mys)    


if __name__ == "__main__":
    s = "Hellothere"
    print(reverseVowels(s))