3775. Reverse Words With Same Vowel Count
Problem Statement
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:
- The first word "cat" has 1 vowel.
- "and" has 1 vowel, so it is reversed to form "dna".
- "mice" has 2 vowels, so it remains unchanged.
- Thus, the resulting string is "cat dna mice".
Example 2
Input: s = "book is nice"
Output: "book is ecin"
Explanation:
- The first word "book" has 2 vowels.
- "is" has 1 vowel, so it remains unchanged.
- "nice" has 2 vowels, so it is reversed to form "ecin".
- Thus, the resulting string is "book is ecin".
Visualization
For s = "cat and mice":
First word vowels: 1 (just 'a')
Second word reversed because it also has 1 vowel
Third word unchanged (2 vowels ≠ 1)
Key Insight
The solution requires careful string processing with these key observations:
- The first word is never reversed - it only serves as the reference for vowel count
- Words are separated by single spaces (no leading/trailing spaces)
- Only lowercase English letters are used
- We need to count vowels in each word and compare with the first word's vowel count
- When reversing, we reverse the entire word, not just the vowels
Important edge cases:
- Single word strings (nothing to reverse)
- Words with no vowels (only consonants)
- Words where vowel count matches but the word is already a palindrome
- Long strings up to 10⁵ characters
Approach 1: String Splitting (Most Intuitive)
Split the string into words, count vowels in first word, then process each subsequent word, reversing when vowel counts match.
Algorithm Steps
- Split the input string by spaces to get an array of words
- Count vowels in the first word (word[0])
- For each word from index 1 to the end:
- Count vowels in the current word
- If vowel count equals first word's vowel count, reverse the word
- Join the words back with spaces and return
How It Works
This approach is straightforward: we isolate each word, count its vowels, and reverse it if needed. The string splitting handles word boundaries for us.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n) | O(n) |
Where n is the length of the string. We traverse the string once to split, then each word once to process. Space is O(n) for storing the word array.
class Solution {
public:
// Helper function to count vowels in a word
int countVowels(const string& word) {
int count = 0;
for (char c : word) {
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
string reverseWordsWithSameVowelCount(string s) {
// Split the string by spaces
vector words;
stringstream ss(s);
string word;
while (ss >> word) {
words.push_back(word);
}
// Count vowels in first word
int firstWordVowelCount = countVowels(words[0]);
// Process remaining words
for (int i = 1; i < words.size(); i++) {
if (countVowels(words[i]) == firstWordVowelCount) {
// Reverse the word
reverse(words[i].begin(), words[i].end());
}
}
// Join words back together
string result;
for (int i = 0; i < words.size(); i++) {
if (i > 0) result += " ";
result += words[i];
}
return result;
}
}; import java.util.*;
class Solution {
// Helper function to count vowels in a word
private int countVowels(String word) {
int count = 0;
for (char c : word.toCharArray()) {
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
public String reverseWordsWithSameVowelCount(String s) {
// Split the string by spaces
String[] words = s.split(" ");
// Count vowels in first word
int firstWordVowelCount = countVowels(words[0]);
// Process remaining words
for (int i = 1; i < words.length; i++) {
if (countVowels(words[i]) == firstWordVowelCount) {
// Reverse the word
words[i] = new StringBuilder(words[i]).reverse().toString();
}
}
// Join words back together
return String.join(" ", words);
}
}class Solution:
def count_vowels(self, word: str) -> int:
# Helper function to count vowels in a word
vowels = set(['a', 'e', 'i', 'o', 'u'])
count = 0
for c in word:
if c in vowels:
count += 1
return count
def reverseWordsWithSameVowelCount(self, s: str) -> str:
# Split the string by spaces
words = s.split()
# Count vowels in first word
first_word_vowel_count = self.count_vowels(words[0])
# Process remaining words
for i in range(1, len(words)):
if self.count_vowels(words[i]) == first_word_vowel_count:
# Reverse the word
words[i] = words[i][::-1]
# Join words back together
return " ".join(words)Approach 2: Two-Pointer In-Place Processing
Process the string without splitting, using two pointers to identify word boundaries and process in-place.
Algorithm Steps
- Find the end of the first word (first space or end of string)
- Count vowels in the first word
- Use two pointers to iterate through the string:
- Pointer
imarks start of current word - Pointer
jfinds end of current word (next space or end)
- Pointer
- For each subsequent word:
- Count vowels between
iandj - If count matches first word, reverse the substring
[i, j)
- Count vowels between
- Move to next word and continue
How It Works
This approach avoids creating an array of words by processing the string in place. We maintain pointers to word boundaries and reverse substrings directly when needed.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n) | O(1) or O(n) for language-specific needs |
Single pass through the string. Space is O(1) for extra variables, though some languages (like Python with immutable strings) need O(n) space.
class Solution {
public:
// Helper function to count vowels in a substring [start, end)
int countVowelsInRange(const string& s, int start, int end) {
int count = 0;
for (int i = start; i < end; i++) {
char c = s[i];
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
// Helper to reverse a substring [start, end) in place
void reverseSubstring(string& s, int start, int end) {
int left = start, right = end - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
string reverseWordsWithSameVowelCount(string s) {
int n = s.length();
// Find end of first word
int firstWordEnd = 0;
while (firstWordEnd < n && s[firstWordEnd] != ' ') {
firstWordEnd++;
}
// Count vowels in first word
int firstWordVowelCount = countVowelsInRange(s, 0, firstWordEnd);
// Process remaining words
int wordStart = firstWordEnd + 1; // Start of next word
while (wordStart < n) {
// Find end of current word
int wordEnd = wordStart;
while (wordEnd < n && s[wordEnd] != ' ') {
wordEnd++;
}
// Count vowels in current word
int currentVowelCount = countVowelsInRange(s, wordStart, wordEnd);
// Reverse if vowel count matches
if (currentVowelCount == firstWordVowelCount) {
reverseSubstring(s, wordStart, wordEnd);
}
// Move to next word
wordStart = wordEnd + 1;
}
return s;
}
};class Solution {
// Helper function to count vowels in a substring [start, end)
private int countVowelsInRange(char[] chars, int start, int end) {
int count = 0;
for (int i = start; i < end; i++) {
char c = chars[i];
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
// Helper to reverse a substring [start, end) in place
private void reverseSubstring(char[] chars, int start, int end) {
int left = start, right = end - 1;
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
}
public String reverseWordsWithSameVowelCount(String s) {
// Convert to char array for in-place modification
char[] chars = s.toCharArray();
int n = chars.length;
// Find end of first word
int firstWordEnd = 0;
while (firstWordEnd < n && chars[firstWordEnd] != ' ') {
firstWordEnd++;
}
// Count vowels in first word
int firstWordVowelCount = countVowelsInRange(chars, 0, firstWordEnd);
// Process remaining words
int wordStart = firstWordEnd + 1; // Start of next word
while (wordStart < n) {
// Find end of current word
int wordEnd = wordStart;
while (wordEnd < n && chars[wordEnd] != ' ') {
wordEnd++;
}
// Count vowels in current word
int currentVowelCount = countVowelsInRange(chars, wordStart, wordEnd);
// Reverse if vowel count matches
if (currentVowelCount == firstWordVowelCount) {
reverseSubstring(chars, wordStart, wordEnd);
}
// Move to next word
wordStart = wordEnd + 1;
}
return new String(chars);
}
}class Solution:
def reverseWordsWithSameVowelCount(self, s: str) -> str:
# Python strings are immutable, so we need to build result
result = []
n = len(s)
# Find end of first word
first_word_end = 0
while first_word_end < n and s[first_word_end] != ' ':
first_word_end += 1
# Count vowels in first word
first_word = s[:first_word_end]
vowels = set(['a', 'e', 'i', 'o', 'u'])
first_word_vowel_count = sum(1 for c in first_word if c in vowels)
# Add first word to result
result.append(first_word)
# Process remaining words
word_start = first_word_end + 1
while word_start < n:
# Find end of current word
word_end = word_start
while word_end < n and s[word_end] != ' ':
word_end += 1
# Get current word
current_word = s[word_start:word_end]
# Count vowels in current word
current_vowel_count = sum(1 for c in current_word if c in vowels)
# Add word to result (reversed if vowel count matches)
if current_vowel_count == first_word_vowel_count:
result.append(current_word[::-1])
else:
result.append(current_word)
# Move to next word
word_start = word_end + 1
return " ".join(result)Approach 3: Stream Processing with StringBuilder
Process the string as a stream, building the result incrementally without storing all words.
Algorithm Steps
- Initialize a StringBuilder/result string and word counter
- Traverse the string character by character:
- Collect characters until a space is encountered
- When space found or end of string reached:
- If first word, count vowels and store count
- If subsequent word, count vowels and reverse if matches
- Add word to result (with space if not first word)
- Return the built result
How It Works
This approach processes the string in a single pass without splitting or creating arrays. It's memory-efficient and works well for streaming scenarios.
Complexity Analysis
| Time Complexity | Space Complexity |
|---|---|
| O(n) | O(n) for output, O(1) extra |
Single pass through the string. Space is O(n) for the output string, with minimal extra variables.
class Solution {
public:
// Helper to count vowels in a string
int countVowels(const string& word) {
int count = 0;
for (char c : word) {
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
// Helper to reverse a string
string reverseString(const string& word) {
string reversed = word;
reverse(reversed.begin(), reversed.end());
return reversed;
}
string reverseWordsWithSameVowelCount(string s) {
string result;
string currentWord;
int wordIndex = 0;
int firstWordVowelCount = -1; // Will be set when we process first word
// Add a space at the end to handle last word uniformly
s += ' ';
for (char c : s) {
if (c == ' ') {
// End of a word
if (!currentWord.empty()) {
int vowelCount = countVowels(currentWord);
if (wordIndex == 0) {
// First word - just store vowel count
firstWordVowelCount = vowelCount;
result += currentWord;
} else {
// Subsequent words - add space then word (maybe reversed)
result += ' ';
if (vowelCount == firstWordVowelCount) {
result += reverseString(currentWord);
} else {
result += currentWord;
}
}
currentWord.clear();
wordIndex++;
}
} else {
// Add character to current word
currentWord += c;
}
}
return result;
}
};class Solution {
public String reverseWordsWithSameVowelCount(String s) {
StringBuilder result = new StringBuilder();
StringBuilder currentWord = new StringBuilder();
int wordIndex = 0;
int firstWordVowelCount = -1; // Will be set when we process first word
// Add a space at the end to handle last word uniformly
s = s + " ";
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') {
// End of a word
if (currentWord.length() > 0) {
String word = currentWord.toString();
int vowelCount = countVowels(word);
if (wordIndex == 0) {
// First word - just store vowel count
firstWordVowelCount = vowelCount;
result.append(word);
} else {
// Subsequent words - add space then word (maybe reversed)
result.append(' ');
if (vowelCount == firstWordVowelCount) {
result.append(new StringBuilder(word).reverse().toString());
} else {
result.append(word);
}
}
currentWord.setLength(0); // Clear the StringBuilder
wordIndex++;
}
} else {
// Add character to current word
currentWord.append(c);
}
}
return result.toString();
}
private int countVowels(String word) {
int count = 0;
for (char c : word.toCharArray()) {
if (c == 'a' || c == 'e' || c == 'i' ||
c == 'o' || c == 'u') {
count++;
}
}
return count;
}
}class Solution:
def reverseWordsWithSameVowelCount(self, s: str) -> str:
result = []
current_word = []
word_index = 0
first_word_vowel_count = -1 # Will be set when we process first word
vowels = set(['a', 'e', 'i', 'o', 'u'])
# Add a space at the end to handle last word uniformly
s = s + " "
for c in s:
if c == ' ':
# End of a word
if current_word:
word = ''.join(current_word)
vowel_count = sum(1 for ch in word if ch in vowels)
if word_index == 0:
# First word - just store vowel count
first_word_vowel_count = vowel_count
result.append(word)
else:
# Subsequent words - word (maybe reversed)
if vowel_count == first_word_vowel_count:
result.append(word[::-1])
else:
result.append(word)
current_word.clear()
word_index += 1
else:
# Add character to current word
current_word.append(c)
return " ".join(result)Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Key Insight | Best Use Case |
|---|---|---|---|---|
| String Splitting | O(n) | O(n) | Simplest, most readable code | General use, interviews, readability matters |
| Two-Pointer In-Place | O(n) | O(1) extra space | Minimizes memory usage, in-place processing | Memory-constrained environments, large strings |
| Stream Processing | O(n) | O(n) output, O(1) extra | Processes as stream, no array storage | Streaming data, incremental processing |
Edge Cases and Testing
1. Single Word
Input: "hello" → Output: "hello"
No other words to compare or reverse2. No Vowels in First Word
Input: "xyz abc def" → Output: "xyz cba fed"
First word "xyz" has 0 vowels
"abc" has 1 vowel → NOT reversed
"def" has 1 vowel → NOT reversed
Wait, correction: Only words with 0 vowels should be reversed
So output: "xyz cba fed" (both "cba" and "fed" have 1 vowel, not 0)3. All Words Same Vowel Count
Input: "cat bat rat" → Output: "cat tab tar"
All words have 1 vowel, so all except first are reversed4. Words with Multiple Same Vowels
Input: "aeiou book test" → Output: "aeiou koob test"
First word "aeiou" has 5 vowels
"book" has 2 vowels → NOT reversed
"test" has 1 vowel → NOT reversed
Actually, "book" has 2 vowels (o, o), so not reversed
"test" has 1 vowel (e), so not reversed5. Palindrome Words
Input: "racecar madam radar" → Output: "racecar madam radar"
First word "racecar" has 3 vowels (a, e, a)
"madam" has 2 vowels (a, a) → NOT reversed
"radar" has 2 vowels (a, a) → NOT reversed
Even if reversed, palindromes look the same6. Very Long String
Input: "a" repeated 50000 times + " b" repeated 50000 times
Output: "aaa... bbb..." (second word reversed if vowel count matches)
Tests performance with 10⁵ charactersDetailed Example Walkthrough
Let's trace through the String Splitting approach with s = "book is nice":
| Step | Action | Words Array | First Word Vowels | Current Word | Vowel Count | Action Taken |
|---|---|---|---|---|---|---|
| 1 | Split string | ["book", "is", "nice"] | - | - | - | Initialize |
| 2 | Count first word vowels | ["book", "is", "nice"] | 2 (o, o) | book | 2 | Store count = 2 |
| 3 | Process "is" | ["book", "is", "nice"] | 2 | is | 1 (i) | 1 ≠ 2 → Leave unchanged |
| 4 | Process "nice" | ["book", "is", "nice"] | 2 | nice | 2 (i, e) | 2 = 2 → Reverse to "ecin" |
| 5 | Join words | ["book", "is", "ecin"] | 2 | - | - | Return "book is ecin" |
Before Processing
Vowel counts: book(2), is(1), nice(2)
After Processing
Result: "book is ecin"
Only "nice" reversed (vowel count = first word's count)
FAQs
1. Why isn't the first word ever reversed?
The problem states: "Determine how many vowels appear in the first word. Then, reverse each following word that has the same vowel count." The first word serves as the reference point. We use its vowel count to decide which subsequent words to reverse.
2. What if the first word has no vowels?
Then we count 0 vowels. Any subsequent word with 0 vowels (i.e., no vowels at all) will be reversed. Words with any vowels will remain unchanged.
3. Are uppercase vowels considered?
No, the problem states the string consists of lowercase English letters only. So we only need to check for lowercase 'a', 'e', 'i', 'o', 'u'.
4. What about the letter 'y'? Is it ever a vowel?
In this problem, 'y' is NOT considered a vowel. Only the five standard vowels 'a', 'e', 'i', 'o', 'u' count. This is specified in the problem statement.
5. Can words have leading or trailing spaces?
No, the constraints state: "s does not contain leading or trailing spaces." Words are separated by single spaces with no extra spaces at the beginning or end.
6. What's the maximum string length we need to handle?
Up to 10⁵ characters according to the constraints. All our O(n) approaches handle this efficiently.
7. How do we handle duplicate vowels in a word?
Each occurrence of a vowel counts separately. For example, "book" has 2 vowels (both 'o'), "beet" has 2 vowels ('e', 'e'), "audio" has 4 vowels ('a', 'u', 'i', 'o').
8. What if two words have the same vowel count but different vowels?
We only care about the count, not which specific vowels. If word1 has 2 vowels ('a', 'e') and word2 has 2 vowels ('i', 'o'), they both have count 2 and word2 would be reversed if it comes after the first word (and first word also has 2 vowels).
9. Can the string be empty?
No, constraints say 1 <= s.length, so the string has at least 1 character. Since it consists of words separated by spaces, the minimum is a single word.
10. What's the most efficient way to check if a character is a vowel?
For this problem with only lowercase letters, a simple if statement checking c == 'a' || c == 'e' etc. is efficient. For case-insensitive checking, you could convert to lowercase first or check both cases. Using a set (in Python) or unordered_set (in C++) is also efficient and clean.