Repeat Code With LeetCode — Reverse Vowels Of A String
Two-Pointer Technique For Days
There are two good solutions to this problem on LeetCode that I am going to draw heavily from. One is this, and the other is this (credit where credit is due, but the second is essentially the same as the first without an explanation).
My only real contribution in this instance is naming all the things I tried that didn’t work.
The Problem
Description
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.
Difficulty: Easy
Skills Required: Two Pointer Technique (depending on implementation)
Some Early Failures
“Reverse Words In A String” is a LeetCode medium, with both a clever two pointer technique solution and a fairly straightforward stack solution. I wondered, could something similar be done here?
If so, I couldn’t find anything. I thought that maybe you could take the vowels, put them in a stack, and then pop them off. But how would you know where to return them? I suppose you could store vowel indices in a vector of pairs, with the first pair element a character and the second pair element the index. I think that this may work in theory, but then I thought about the Two Pointer Technique.
Set one pointer to the start of your string, and one pointer to the end. Every time both indies happen on a vowel, swap them.
Even after arriving at the most popular approach, I ran into syntax errors.
The Solution
The first thing to note here is that my isVowel function is not elegant. It accepts a character, and it checks to see if the character is a cap or lowercase vowel via hard-coding. Most people opted for a set or “reference string” in this case, but I don’t know if a hard-coded check is much less efficient (the code is less readable, though).
One thing that tripped me up was the “pointer movement.” I set a leftPointer < rightPointer condition, as is typical in these Two Pointer Technique problems, but I only moved both at the end of the while loop. The problem there is that this would only work in instances where vowels perfectly mirror each other. This is not a valid assumption. If the first vowel from the right is the third to last character, and the first vowel from the left is the second character, you need to swap them.
So I did something a bit like what you see above, only I did not realize both while loops need to once again check that left < right. If you do not enforce this condition again, test cases will fail.
Move both pointers as long as they are NOT vowels (ie they are consonants), and those nested while loops will get your pointers into position. Swap them, adjust the pointers, and exit your while loop. Your outer while loop will proceed until you reach the center.
Closing Thoughts
Someone wrote a popular comment on this that they were interviewing seniors with more than 10 years of experience, and the senior engineers still struggled.
This is a great question. You would be suprised how many senior devs with 10+ years of experience have stuttered and stumbled during a real interview with this question. This may be easy for many of you, but every question teaches us something. As a batter in cricket, we are taught to respect every ball, same applies to leetcode too, respect every question, it only takes 1 question to bowl us out.
— https://leetcode.com/problems/reverse-vowels-of-a-string/description/
The reason for their struggle, the comment concludes, is that they underestimated the question. In cricket, they teach that we must respect every ball, for it takes only one to bowl us out.
The time we spent solving this LeetCode could also have been spent playing Cricket. Then we would gain exercise, well-rounded insight, and the wisdom to leave helpful life lessons in the comments section of LeetCode.
