Watch 10 video solutions for Reverse Words With Same Vowel Count, a medium level problem involving Two Pointers, String, Simulation. This walkthrough by yoBro has 308 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting of lowercase English words, each separated by a single space.
Determine how many vowels appear in the first word. Then, reverse each following word that has the same vowel count. Leave all remaining words unchanged.
Return the resulting string.
Vowels are 'a', 'e', 'i', 'o', and 'u'.
Example 1:
Input: s = "cat and mice"
Output: "cat dna mice"
Explanation:
"cat" has 1 vowel."and" has 1 vowel, so it is reversed to form "dna"."mice" has 2 vowels, so it remains unchanged."cat dna mice".Example 2:
Input: s = "book is nice"
Output: "book is ecin"
Explanation:
"book" has 2 vowels."is" has 1 vowel, so it remains unchanged."nice" has 2 vowels, so it is reversed to form "ecin"."book is ecin".Example 3:
Input: s = "banana healthy"
Output: "banana healthy"
Explanation:
"banana" has 3 vowels."healthy" has 2 vowels, so it remains unchanged."banana healthy".
Constraints:
1 <= s.length <= 105s consists of lowercase English letters and spaces.s are separated by a single space.s does not contain leading or trailing spaces.Problem Overview: You receive a sentence containing multiple words separated by spaces. The task is to reverse the order of words that have the same number of vowels while keeping the rest of the sentence structure intact.
Approach 1: Direct Simulation (O(n) time, O(n) space)
Split the sentence into a list of words using the space delimiter. For each word, compute the vowel count by iterating through its characters and checking membership in a vowel set such as {a,e,i,o,u}. Maintain a mapping from vowel count to the list of indices where those words appear. Once all words are processed, iterate through each index list and reverse the corresponding words in place by swapping elements from both ends of the list.
This works because words with the same vowel count form independent groups. Reversing the indices inside each group changes their relative order without affecting other words. The algorithm scans the sentence once to compute counts and once more to perform swaps, giving O(n) total time where n is the number of characters (or words depending on implementation). Extra storage for the mapping and split words results in O(n) space.
Approach 2: Two Pointers on Vowel Groups (O(n) time, O(n) space)
After computing the vowel count for each word, store the indices of words for each vowel count in an array or hash map. For every group of indices, apply a classic Two Pointers technique: place one pointer at the start and another at the end of the index list, then swap the words at those positions while moving both pointers inward.
This avoids creating intermediate reversed lists and keeps operations strictly in-place on the word array. The main operations are simple index lookups and swaps, making the approach efficient and easy to implement using basic String manipulation and Simulation. The complexity remains O(n) time and O(n) auxiliary space due to the grouped indices.
Recommended for interviews: The grouped simulation with two pointers is the expected solution. It demonstrates that you can preprocess the input, categorize elements by a computed property (vowel count), and then apply in‑place reversal efficiently. A brute-force idea might attempt repeated scans to find matching vowel counts, but the grouped approach shows stronger algorithmic thinking and keeps the runtime linear.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Re-scanning | O(n^2) | O(1) | Conceptual baseline when first reasoning about matching vowel counts |
| Simulation with Vowel Count Mapping | O(n) | O(n) | General solution; easy to implement and clearly groups words by vowel count |
| Two Pointers on Index Groups | O(n) | O(n) | Preferred implementation when reversing each vowel-count group efficiently |