LeetCode Entry

3227. Vowels Game in a String

12.09.2025 medium 2025 kotlin rust

Can Alice win Bob both removeing odd-even vowel count substring optimally

3227. Vowels Game in a String medium blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1110

Problem TLDR

Can Alice win Bob both removeing odd-even vowel count substring optimally #medium

Intuition

Naive dp: at every position i check every position j=i..n if the tail is loosing. Optimization trick: check in reverse j=n..i to end game faster

Approach

  • the final solution is that Alice always wins: odd on the first move, even - on the third

Complexity

  • Time complexity: \(O(n^2)\), or O(n)

  • Space complexity: \(O(n)\), or O(1)

Code


// 16ms
    fun doesAliceWin(s: String) =
        "[aeiou]".toRegex() in s



// 33ms
    fun doesAliceWin(s: String): Boolean {
        val f = IntArray(s.length)
        for ((i, c) in s.withIndex()) f[i] = f[max(0, i-1)] + if (c in "aeiou") 1 else 0
        val dp = HashMap<Pair<Int, Boolean>, Boolean>()
        fun dfs(i: Int, odd: Boolean): Boolean =
        i < s.length && dp.getOrPut(i to odd) {
            for (j in s.length-1 downTo i) {
                var cnt = f[j] - (if (i > 0) f[i-1] else 0)
                if (odd == (cnt % 2 > 0))
                if (!dfs(j+1, !odd)) return@getOrPut true
            }
            false
        }
        return dfs(0, true)
    }



// 3ms
    pub fn does_alice_win(s: String) -> bool {
        s.chars().any(|c| "aeiou".contains(c))
    }