{x}
blog image

Determine if String Halves Are Alike

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.

 

Example 1:

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

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

 

Constraints:

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

Solution Explanation

This problem asks whether the number of vowels in the first half of a string is equal to the number of vowels in the second half. The solution uses a counting approach.

Approach:

  1. Initialization: We create a set vowels containing all uppercase and lowercase vowels. This allows for O(1) lookup time when checking if a character is a vowel. We also initialize a counter cnt to 0 and calculate n, which is half the length of the input string s.

  2. Iteration: We iterate through the first half of the string (from index 0 to n-1). For each character:

    • If the character is a vowel, we increment cnt.
    • We also check the corresponding character in the second half of the string (at index i + n). If it's a vowel, we decrement cnt.

  3. Comparison: After iterating through the first half, if cnt is 0, it means the number of vowels in the first half equals the number of vowels in the second half. We return true in this case; otherwise, we return false.

Time Complexity: O(n), where n is the length of the string. We iterate through half the string once.

Space Complexity: O(1). The space used by the vowels set is constant, regardless of the input string's length. The other variables (cnt, n) use constant space.

Code Explanation (Python3 as an example)

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        cnt, n = 0, len(s) >> 1 # n = len(s)//2 (bitwise right shift is efficient)
        vowels = set('aeiouAEIOU') #Efficient vowel check using a set
        for i in range(n):
            cnt += s[i] in vowels  # Increment if vowel in first half
            cnt -= s[i + n] in vowels # Decrement if vowel in second half
        return cnt == 0 # True if counts are equal, False otherwise

This code directly implements the approach described above. The use of a set for vowels and the bitwise right shift for calculating n are optimizations for efficiency. The concise loop efficiently counts the differences in vowel occurrences between both halves.

The other language solutions provided in the original response follow the same algorithm and differ only in syntax specific to their respective languages. They all maintain the same time and space complexity.