Difficulty: 🟢 Easy
Topics: String, Counting

Solution

Determine if String Halves Are Alike

Problem Understanding

The problem gives us a string s whose length is guaranteed to be even. We split the string into two equal parts:

The first half is called a
The second half is called b

We must determine whether both halves contain the same number of vowels. The vowels include both lowercase and uppercase English vowels:

Lowercase: a, e, i, o, u
Uppercase: A, E, I, O, U

If both halves contain the same vowel count, we return true. Otherwise, we return false.

For example, if the input is "book":

First half: "bo"
Second half: "ok"

Each half contains exactly one vowel (o), so the answer is true.

The constraints are small:

2 <= s.length <= 1000
The string length is always even
The string contains only uppercase and lowercase letters

Because the maximum length is only 1000, even relatively simple solutions will work efficiently. However, we can still design an optimal linear-time solution with constant extra space.

An important observation is that the problem only cares about the number of vowels, not their positions. We do not need to store substrings or perform complicated comparisons.

There are several edge cases worth considering:

Strings with no vowels at all, both halves would have zero vowels and therefore be alike.
Strings where vowels appear multiple times, every occurrence must be counted separately.
Mixed uppercase and lowercase letters, we must correctly recognize vowels in both cases.
Very short strings such as length 2, where each half contains only one character.

Approaches

Brute Force Approach

A straightforward solution is to explicitly split the string into two substrings:

Create the first half
Create the second half
Count vowels in each half independently
Compare the counts

This works because counting vowels separately guarantees an accurate comparison.

Although this solution is already efficient enough for the constraints, it creates additional substring objects and performs two separate traversals.

Optimal Approach

A better approach is to process both halves in a single pass.

Instead of counting vowels separately with two loops, we can maintain a running balance:

Add 1 when we see a vowel in the first half
Subtract 1 when we see a vowel in the second half

At the end:

If the balance is 0, both halves contain the same number of vowels
Otherwise, they are different

This avoids storing substrings and keeps the solution concise and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Creates substrings and counts vowels separately
Optimal	O(n)	O(1)	Single traversal with running vowel balance

Algorithm Walkthrough

Optimal Algorithm

Create a set containing all vowels, both uppercase and lowercase.
Compute the midpoint of the string using len(s) // 2. Since the problem guarantees an even length, this cleanly divides the string into two equal halves.
Initialize a variable called balance to 0. This variable tracks the difference between vowel counts in the two halves.
Traverse the string from index 0 to len(s) - 1.
For each character:

If the character is not a vowel, ignore it.
If it is a vowel:
Add 1 to balance if the character belongs to the first half.
Subtract 1 from balance if the character belongs to the second half.

After the traversal finishes:

Return True if balance == 0
Otherwise return False

Why it works

The algorithm maintains the invariant that balance always equals:

(number of vowels in first half processed so far)
-
(number of vowels in second half processed so far)

Every vowel in the first half increases the balance, and every vowel in the second half decreases it. If both halves contain the same total number of vowels, the final balance must be zero. Therefore, checking balance == 0 correctly determines whether the halves are alike.

Python Solution

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set("aeiouAEIOU")
        half = len(s) // 2
        balance = 0

        for index, char in enumerate(s):
            if char in vowels:
                if index < half:
                    balance += 1
                else:
                    balance -= 1

        return balance == 0

The solution begins by creating a set of vowels. A set provides average O(1) lookup time, making vowel checks efficient.

The variable half stores the midpoint of the string. Since the length is guaranteed to be even, indices before half belong to the first half, and indices from half onward belong to the second half.

The balance variable tracks the difference in vowel counts. During iteration:

Vowels in the first half increase the balance
Vowels in the second half decrease the balance

At the end, a balance of zero means both halves contain the same number of vowels.

This implementation avoids creating temporary substrings and processes the input in a single pass.

Go Solution

func halvesAreAlike(s string) bool {
    vowels := map[byte]bool{
        'a': true,
        'e': true,
        'i': true,
        'o': true,
        'u': true,
        'A': true,
        'E': true,
        'I': true,
        'O': true,
        'U': true,
    }

    half := len(s) / 2
    balance := 0

    for i := 0; i < len(s); i++ {
        if vowels[s[i]] {
            if i < half {
                balance++
            } else {
                balance--
            }
        }
    }

    return balance == 0
}

The Go implementation follows the same logic as the Python solution. Instead of using a set, Go uses a map[byte]bool to represent vowels.

Strings in Go are indexed by bytes, which works correctly here because the input contains only English alphabet characters.

The solution uses a single traversal and constant extra memory.

Worked Examples

Example 1

Input: s = "book"

The string length is 4, so:

First half: "bo"
Second half: "ok"

Index	Character	Vowel?	Half	Balance
0	b	No	First	0
1	o	Yes	First	1
2	o	Yes	Second	0
3	k	No	Second	0

Final balance is 0, so the result is true.

Example 2

Input: s = "textbook"

The string length is 8, so:

First half: "text"
Second half: "book"

Index	Character	Vowel?	Half	Balance
0	t	No	First	0
1	e	Yes	First	1
2	x	No	First	1
3	t	No	First	1
4	b	No	Second	1
5	o	Yes	Second	0
6	o	Yes	Second	-1
7	k	No	Second	-1

Final balance is -1, so the result is false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	The vowel set has fixed size regardless of input

The algorithm performs a single linear scan through the string. Each vowel lookup is constant time on average, so the overall runtime is proportional to the string length.

The extra memory usage remains constant because the vowel collection always contains exactly ten characters.

Test Cases

solution = Solution()

assert solution.halvesAreAlike("book") == True      # equal vowel counts
assert solution.halvesAreAlike("textbook") == False # second half has more vowels
assert solution.halvesAreAlike("AbCdEfGh") == True  # mixed uppercase and lowercase vowels
assert solution.halvesAreAlike("bcdfBCDF") == True  # no vowels in either half
assert solution.halvesAreAlike("aaAA") == True      # all vowels, balanced halves
assert solution.halvesAreAlike("aAab") == False     # first half has more vowels
assert solution.halvesAreAlike("MerryChristmas") == False # uneven vowel distribution
assert solution.halvesAreAlike("xY") == True        # smallest valid length, no vowels
assert solution.halvesAreAlike("uU") == True        # smallest valid length, both vowels
assert solution.halvesAreAlike("aeioBCDF") == False # all vowels concentrated in first half

Test	Why
`"book"`	Validates the basic balanced case
`"textbook"`	Validates unequal vowel counts
`"AbCdEfGh"`	Confirms uppercase vowels are handled
`"bcdfBCDF"`	Tests strings with zero vowels
`"aaAA"`	Tests fully vowel-based input
`"aAab"`	Tests imbalance favoring first half
`"MerryChristmas"`	Tests a more realistic mixed string
`"xY"`	Tests minimum input size with no vowels
`"uU"`	Tests minimum input size with vowels
`"aeioBCDF"`	Tests all vowels appearing in one half

Edge Cases

Strings With No Vowels

An input such as "bcdfBCDF" contains no vowels in either half. A buggy implementation might incorrectly assume at least one vowel exists. This solution handles the case naturally because the balance never changes from zero.

Mixed Uppercase and Lowercase Letters

The problem explicitly states that vowels may appear in uppercase or lowercase form. An implementation that only checks lowercase vowels would fail for inputs like "AbCdEfGh". This solution includes both uppercase and lowercase vowels in the lookup set.

Multiple Repeated Vowels

Inputs such as "textbook" contain repeated vowels. Every vowel occurrence must be counted individually. A naive implementation using unique vowel tracking would produce incorrect results. This algorithm processes every character independently, so repeated vowels are counted correctly.

Minimum Length Strings

The smallest valid input length is 2. Examples include "xY" and "uU". Some implementations may incorrectly handle indexing or midpoint calculations for very short strings. Since the midpoint is computed using integer division and the loop handles all indices uniformly, these cases work correctly.

LeetCode 1704 - Determine if String Halves Are Alike