Determine if String Halves Are Alike

Difficulty: Easy | Acceptance: 78.80% | Paid: No Topics: String, Counting

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

• Examples
• Constraints
• Two Pass Counting
• Single Pass with Counter
• Simultaneous Half Comparison

Examples

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Input: s = "textbook"
Output: false
Explanation: a = "tex" and b = "tbook". a has 1 vowel and b has 2 vowels. Therefore, they are not alike.

Constraints

2 <= s.length <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Two Pass Counting

Intuition Split the string into two halves and count vowels in each half separately, then compare the counts.

Steps

• Calculate the midpoint of the string
• Count vowels in the first half
• Count vowels in the second half
• Return true if counts are equal

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) for the vowel set/string
• Notes: Simple and readable approach with two separate loops

Single Pass with Counter

Intuition Use a single counter that increments for vowels in the first half and decrements for vowels in the second half. If the counter is zero at the end, both halves have equal vowels.

Steps

• Initialize a counter to zero
• Iterate through the entire string
• Increment counter for vowels in first half, decrement for vowels in second half
• Return true if counter equals zero

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set('aeiouAEIOU')
        n = len(s)
        half = n // 2
        count = 0
        
        for i in range(n):
            if s[i] in vowels:
                if i < half:
                    count += 1
                else:
                    count -= 1
        
        return count == 0

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) for the vowel set/string
• Notes: Single loop but requires conditional check for half position

Simultaneous Half Comparison

Intuition Iterate only through the first half and simultaneously check corresponding characters from both halves, counting vowels in each.

Steps

• Calculate the midpoint
• Iterate from 0 to midpoint
• Check character at position i (first half) and i + midpoint (second half)
• Count vowels in both halves
• Compare counts at the end

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

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) for the vowel set/string
• Notes: Most efficient - only iterates through half the string length