LeetCode 3775 - Reverse Words With Same Vowel Count

The problem requires processing a string s consisting of lowercase English words separated by single spaces. The first task is to count the number of vowels in the first word.

leetcodemediumtwo-pointersstringsimulation

LeetCode Problem 3775

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Simulation

Solution

Problem Understanding

The problem requires processing a string s consisting of lowercase English words separated by single spaces. The first task is to count the number of vowels in the first word. Then, for each subsequent word in the string, if the word has the same number of vowels as the first word, it should be reversed. Words with a different number of vowels remain unchanged. Finally, all the words are recombined into a single string separated by spaces, which is returned.

The input string s is guaranteed to be non-empty and contains only lowercase English letters and spaces. Words are separated by exactly one space, and there are no leading or trailing spaces. The length of s can be up to 100,000 characters, so any solution must handle long strings efficiently.

Edge cases include strings with only one word, strings where no other word matches the vowel count of the first word, and strings where all subsequent words match the vowel count and need reversing.

Approaches

A brute-force approach would iterate over the words, count vowels for each word individually, and reverse matching words. This works correctly, but it may involve repeated vowel-counting operations, which could be inefficient for long strings.

The optimal approach recognizes that counting vowels in each word is cheap and uses Python or Go string splitting and joining efficiently. By first counting vowels in the first word and then iterating once through the rest of the words, reversing only when necessary, we can achieve a linear time solution in terms of the total length of the string.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Count vowels separately for each word; may do repeated operations.
Optimal O(n) O(n) Count vowels once per word, reverse selectively, and reconstruct the string efficiently.

Here, n is the total length of the string s, and m is the average word length.

Algorithm Walkthrough

  1. Split the input string s into words using space as the delimiter. This produces a list of words.
  2. Count the number of vowels in the first word. Maintain a set of vowels {'a','e','i','o','u'} for fast lookup.
  3. Iterate over the remaining words:
  • For each word, count its vowels.
  • If the vowel count matches that of the first word, reverse the word.
  • Otherwise, leave it unchanged.
  1. After processing all words, join the list back into a string with single spaces separating words.
  2. Return the resulting string.

Why it works: The algorithm preserves the original word order and selectively reverses only the words that match the first word’s vowel count. By processing each word independently, it guarantees correctness for all valid inputs.

Python Solution

class Solution:
    def reverseWords(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        words = s.split()
        
        def count_vowels(word: str) -> int:
            return sum(1 for ch in word if ch in vowels)
        
        first_vowel_count = count_vowels(words[0])
        
        for i in range(1, len(words)):
            if count_vowels(words[i]) == first_vowel_count:
                words[i] = words[i][::-1]
        
        return ' '.join(words)

The implementation splits the string into words, counts vowels in the first word, and iterates through the rest to reverse words as needed. The helper function count_vowels makes the code readable and avoids repeated logic.

Go Solution

import "strings"

func reverseWords(s string) string {
    vowels := "aeiou"
    words := strings.Split(s, " ")
    
    countVowels := func(word string) int {
        count := 0
        for _, ch := range word {
            if strings.ContainsRune(vowels, ch) {
                count++
            }
        }
        return count
    }
    
    firstVowelCount := countVowels(words[0])
    
    for i := 1; i < len(words); i++ {
        if countVowels(words[i]) == firstVowelCount {
            runes := []rune(words[i])
            for l, r := 0, len(runes)-1; l < r; l, r = l+1, r-1 {
                runes[l], runes[r] = runes[r], runes[l]
            }
            words[i] = string(runes)
        }
    }
    
    return strings.Join(words, " ")
}

The Go implementation mirrors the Python approach. It uses strings.Split to tokenize, a local function countVowels to count vowels, and rune slices to reverse words, which correctly handles Unicode-safe operations even though the problem only specifies lowercase ASCII.

Worked Examples

Example 1: s = "cat and mice"

Word Vowel Count Action Result
cat 1 first word cat
and 1 matches dna
mice 2 does not match mice

Output: "cat dna mice"

Example 2: s = "book is nice"

Word Vowel Count Action Result
book 2 first word book
is 1 does not match is
nice 2 matches ecin

Output: "book is ecin"

Example 3: s = "banana healthy"

Word Vowel Count Action Result
banana 3 first word banana
healthy 2 does not match healthy

Output: "banana healthy"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Splitting, counting vowels, and reversing each word are all linear in total string length n.
Space O(n) Storing the split words and intermediate reversed words requires space proportional to input length.

The algorithm iterates over each character of the input at most twice: once to split and count vowels, once to reverse words, giving linear overall time.

Test Cases

# test cases
assert Solution().reverseWords("cat and mice") == "cat dna mice"  # example 1
assert Solution().reverseWords("book is nice") == "book is ecin"  # example 2
assert Solution().reverseWords("banana healthy") == "banana healthy"  # example 3
assert Solution().reverseWords("a e i o u") == "a e i o u"  # all single letters, only first is compared
assert Solution().reverseWords("aa aa aa") == "aa aa aa"  # all match first word
assert Solution().reverseWords("xyz bc def") == "xyz bc def"  # no vowels match
assert Solution().reverseWords("hello") == "hello"  # single word input
Test Why
"cat and mice" matches example, simple case
"book is nice" matches example with reversal in the last word
"banana healthy" no words match first word vowel count
"a e i o u" single-character words, mostly unchanged
"aa aa aa" all words match first word, but reversing identical strings does not change them
"xyz bc def" no vowels in any word, ensuring no false matches
"hello" single word input, should remain unchanged

Edge Cases

The first edge case is a single-word string. Since there are no subsequent words, no reversal occurs. The implementation handles this naturally by iterating starting from index 1, so the first word is never reversed.

A second edge case is a string where no other word matches the first word's vowel count. This tests that the algorithm does not mistakenly reverse words. By comparing vowel counts individually, it avoids any false positives.

A third edge case involves words with identical vowel counts to the first word but palindromic content. Reversing a palindrome yields the same string, which could mislead a naive implementation that checks identity rather than actual reversal. Our approach always performs the reversal operation when counts match, preserving correctness.