algoadvance

LeetCode Problem 1704: Determine if String Halves Are Alike

You are given a string s of even length. Split this string into two halves of the same length, and determine if these halves are “alike”. Two strings are considered alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Note that the string is assumed to contain only ASCII characters.

Return true if the two halves are alike, and false otherwise.

Example

Input: s = "book"
Output: true
Explanation: "bo" and "ok" both have 1 vowel so they are alike.

Input: s = "textbook"
Output: false
Explanation: "text" has 1 vowel and "book" has 2 vowels, so they are not alike.

Clarifying Questions

1. Is the input string guaranteed to be in even length?
   • Yes, the problem states that the string will always be of even length.
2. What characters are considered vowels?
   • The characters ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ and their uppercase counterparts ‘A’, ‘E’, ‘I’, ‘O’, ‘U’ are considered vowels.
3. Is the input only composed of ASCII characters?
   • Yes, the problem specifies that the string contains only ASCII characters.

Strategy

1. Splitting the String:
   • Given s, find its length n, compute the midpoint m = n // 2.
   • Split the string into two halves: first_half = s[:m], second_half = s[m:].
2. Counting Vowels:
   • Define a set of vowels: vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}.
   • Create a function to count vowels in a given string by iterating and checking membership in the vowels set.
3. Comparison:
   • Compare the number of vowels in both halves and return True if they are the same, otherwise False.

Code

def halvesAreAlike(s):
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    
    def count_vowels(substring):
        return sum(1 for char in substring if char in vowels)
    
    n = len(s)
    m = n // 2
    first_half = s[:m]
    second_half = s[m:]
    
    return count_vowels(first_half) == count_vowels(second_half)

# Test cases
print(halvesAreAlike("book"))      # Output: True
print(halvesAreAlike("textbook"))  # Output: False
print(halvesAreAlike("AbCdEfGh"))  # Output: False
print(halvesAreAlike("aA"))        # Output: True

Time Complexity

• Splitting the string: O(1) since slicing operations are fast and done in constant time.
• Counting vowels: O(n) where n is the length of the string. Each character is checked exactly once, so it runs in linear time.

Thus, the overall time complexity of this function is O(n).

By following this strategy, we ensure that the two halves of the given string s are validated with respect to their vowel content efficiently.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?