1704. Determine if String Halves Are Alike
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 78.9%
Problem Breakdown
The problem requires us to determine if two halves of a given string have an equal number of vowels. The input is a string s of even length. We need to split the string into two halves and count the vowels in each half. If both halves have the same number of vowels, return true; otherwise, return false.
Inputs:
- A string
swith an even length.
Outputs:
- A boolean value (
trueorfalse) indicating whether the two halves of the string have the same number of vowels.
Implicit Constraints/Edge Cases:
- The string contains only uppercase and lowercase letters.
- The length of the string is guaranteed to be even, so no need to handle odd lengths.
- The string could contain no vowels at all, which should still be handled correctly.
Intuition
A brute-force approach would involve splitting the string into two halves, iterating through each half to count the vowels, and then comparing the counts. This approach is straightforward but not optimal in terms of time complexity since it involves iterating over the entire string twice.
The key insight is that we can optimize this by using a single pass through the string while maintaining counters for both halves simultaneously. This reduces the time complexity from O(2n) to O(n).
Approach
- Initialize Counters: Start with two counters,
count_aandcount_b, initialized to zero. These will keep track of the number of vowels in the first and second halves of the string, respectively. - Iterate Through the String: Loop through each character in the string.
- For characters in the first half (indices 0 to n/2 - 1), increment
count_aif the character is a vowel. - For characters in the second half (indices n/2 to n - 1), increment
count_bif the character is a vowel.
- For characters in the first half (indices 0 to n/2 - 1), increment
- Compare Counters: After processing all characters, compare
count_aandcount_b. If they are equal, returntrue; otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We make a single pass through the string.
- Space Complexity: O(1). We use only a constant amount of extra space for the counters.
Solution
def halvesAreAlike(s: str) -> bool:
vowels = set('aeiouAEIOU')
count_a, count_b = 0, 0
n = len(s)
for i in range(n):
if s[i] in vowels:
if i < n // 2:
count_a += 1
else:
count_b += 1
return count_a == count_b
Edge Cases Handled
- No Vowels: If there are no vowels in the string, both counters will remain zero, and the function will correctly return
true. - All Characters Are Vowels: The function will correctly count all vowels and compare the counts for both halves.
- Mixed Case Vowels: The function handles both uppercase and lowercase vowels by using a set that includes both cases.