Problem 1704

(Last updated: )

Question statement:

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.

Solution:

Main idea:

To deal with the case sensitivity, we first turn the string to all lower case symbols.

Brute force approach: We split the string into two halves. Initialize two counters to 0. Traverse through the two substrings, updating the counter everytime a vowel is encountered. Finally return counter1==counter2.

Brute force but cheeky approach: We can do the above in a single pass via a two pointer approach. Initialize the first pointer to index 0, and the second pointer to the midpoint (mid) of the string. As the index ranges from 0 to mid, update counter by +1 if a vowel is encountered at s[i] and update it by -1 if a vowel is encountered at s[mid+i]. Finally, return counter == 0.

Code:

Brute force:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def halvesAreAlike(self, s: str) -> bool:
    vowels = set(['a','e','i','o','u'])
    half_index = len(s)//2
    a = s[:half_index] 
    b= s[half_index:]
    count_a = 0
    count_b = 0
    for i in a:
        if(i.lower() in vowels):
            count_a +=1
        else:
            continue
    for i in b:
        if(i.lower() in vowels):
            count_b +=1
        else:
            continue
    return count_a == count_b

Brute force but cheeky:

1
2
3
4
5
6
7
8
9
10
11
def halvesAreAlike(self, s: str) -> bool:
    s=s.lower()
    mid = len(s)//2
    vowels = set(['a','e','i','o','u'])
    count = 0
    for i in range(mid):
        if(s[i] in vowels):
            count +=1
        if(s[mid + i] in vowels):
            count -=1
    return count == 0

Comments:

Time complexity for both approaches: O(n)

At the time of submission, the first solution passes leetcode submission cases in 36ms, beats 87.10% of users. It uses 17.46MB of memory, beating 9.07% of users.
At the time of submission, the second solution passes leetcode submission cases in 35ms, beats 90.17% of users. It uses 17.20MB of memory, beating 33.46% of users.