We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Determine if String Halves Are Alike

Number: 1823

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given an even-length string s, split the string into two equal halves a and b. The goal is to check whether the number of vowels (a, e, i, o, u in both uppercase and lowercase) in both halves is the same.

Key Insights

  • Split the string into two equal parts.
  • Define a set of vowels for quick lookup.
  • Count the vowels in each half individually.
  • Compare the vowel counts to determine if the halves are "alike".

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as the string is traversed twice at most. Space Complexity: O(1), since the extra space used (set of vowels and counters) does not scale with input size.

Solution

Use a two-step approach:

  1. Split the string at the midpoint.
  2. Count vowels in each half using a vowel set for constant-time checks.
  3. Check if the two counts are equal.

Data structures used include a set (or similar fast lookup structure) for vowels. The algorithm relies on iterating over each half once, yielding linear time complexity, which is efficient given the problem constraints.

Code Solutions

def halvesAreAlike(s):
    # Define a set of vowels for constant-time lookup
    vowels = set("aeiouAEIOU")
    n = len(s)
    # Count vowels in the first half using a generator expression
    first_half_vowels = sum(1 for char in s[:n//2] if char in vowels)
    # Count vowels in the second half similarly
    second_half_vowels = sum(1 for char in s[n//2:] if char in vowels)
    # Return True if both halves have the same number of vowels
    return first_half_vowels == second_half_vowels

# Example usage:
print(halvesAreAlike("book"))   # Expected output: True
print(halvesAreAlike("textbook"))  # Expected output: False
← Back to All Questions