Code Implementation

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set('aeiouAEIOU')
        n = len(s)
        half = n // 2
        count1 = sum(1 for c in s[:half] if c in vowels)
        count2 = sum(1 for c in s[half:] if c in vowels)
        return count1 == count2
      

class Solution {
public:
    bool halvesAreAlike(string s) {
        string vowels = "aeiouAEIOU";
        int n = s.size(), half = n / 2;
        int count1 = 0, count2 = 0;
        for (int i = 0; i < half; ++i)
            if (vowels.find(s[i]) != string::npos) ++count1;
        for (int i = half; i < n; ++i)
            if (vowels.find(s[i]) != string::npos) ++count2;
        return count1 == count2;
    }
};
      

class Solution {
    public boolean halvesAreAlike(String s) {
        String vowels = "aeiouAEIOU";
        int n = s.length(), half = n / 2;
        int count1 = 0, count2 = 0;
        for (int i = 0; i < half; i++)
            if (vowels.indexOf(s.charAt(i)) != -1) count1++;
        for (int i = half; i < n; i++)
            if (vowels.indexOf(s.charAt(i)) != -1) count2++;
        return count1 == count2;
    }
}
      

var halvesAreAlike = function(s) {
    const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
    let n = s.length, half = n / 2;
    let count1 = 0, count2 = 0;
    for (let i = 0; i < half; i++) {
        if (vowels.has(s[i])) count1++;
    }
    for (let i = half; i < n; i++) {
        if (vowels.has(s[i])) count2++;
    }
    return count1 === count2;
};
      

Problem Description

Given a string s of even length, split it into two halves: the first half a and the second half b. A string is considered "alike" if both halves contain the same number of vowels. Vowels are defined as the characters 'a', 'e', 'i', 'o', 'u' (both uppercase and lowercase).

Your task is to determine if the two halves of s are alike, that is, if both halves have the same number of vowels.

• The length of s is always even.
• Return true if the halves are alike, otherwise false.

Thought Process

At first glance, the problem is about comparing the number of vowels in two halves of a string. A brute-force approach would be to split the string, count vowels in each half, and compare the counts.

However, we can optimize by avoiding unnecessary string splits and using efficient data structures for vowel lookups. Since the string's length is guaranteed to be even, dividing it into two equal halves is straightforward. The main challenge is to count vowels efficiently and compare the results.

Using a set for vowels allows O(1) lookup for each character, making our solution faster. The overall process is simple, but being mindful of time and space complexity is important for larger inputs.

Solution Approach

• Step 1: Define the set of vowels, including both uppercase and lowercase characters, for quick lookup.
• Step 2: Calculate the midpoint of the string, which is half its length.
• Step 3: Iterate through the first half of the string and count the number of vowels.
• Step 4: Iterate through the second half and count the vowels there as well.
• Step 5: Compare the two counts. If they are equal, return true; otherwise, return false.

We use a set for vowels to ensure that checking if a character is a vowel takes constant time. This makes our solution efficient and easy to understand.

Example Walkthrough

Let's consider the example s = "book":

• Length of s is 4. Midpoint is 2.
• First half: "bo"
• Second half: "ok"

Counting vowels:

• First half: 'b' (not a vowel), 'o' (vowel) → 1 vowel
• Second half: 'o' (vowel), 'k' (not a vowel) → 1 vowel

Since both halves have 1 vowel each, the function returns true.

Time and Space Complexity

• Brute-force approach: Split the string, count vowels in each half. Time complexity is O(n), where n is the length of the string, since every character is checked. Space complexity is O(n) if splitting creates new strings.
• Optimized approach: Use indices to check each character without creating new strings. Still O(n) time, but space complexity is O(1) (ignoring the small constant space for the set of vowels).

The optimized approach is preferred because it minimizes extra space and is efficient even for large strings.

Summary

To determine if the two halves of a string are alike, we efficiently count vowels in both halves using a set for quick lookup. The solution is clean, avoids unnecessary string operations, and runs in linear time with constant extra space. This approach demonstrates the value of simple optimizations and careful use of data structures in string processing problems.