Algorithmic problems: Determine if String Halves Are Alike

Let's kick off this blog with December leetcoding challenges first problem https://leetcode.com/problems/determine-if-string-halves-are-alike/. This is an Easy category problem which mainly tells us that

Problem breakdown

If we divide a string into two halves return True if the number of vowels in both halves is equal else return False.

My approach

This appeared as a counting problem and we need a way to refer to items that we need to count which are the vowels in this case, so we need a way to store them and we also need a good strategy to count the vowels. Note: Duplicates in either half are counted distinctly.

Data Structures used

set since we need to go over the list of vowels over gain it is most efficient to use a set compared to list since they take lesser time for searching. We also, take two variables to store the vowel counts of both halves.

Algorithms/ methods used

I used two pointer technique to over the halves from front to back in a single iteration to search the string and compare with the vowel set as we go. If any of the chars encountered is in the set we increment the corresponding counter, regardless of the comparisons in each step we increment the first pointer to move one step forward and the other counter to move one step backward. Eventually, they keep moving until they reach each other which is the breaking condition of our loop.

def halvesAreAlike(self, s: str) -> bool:
    vowel_str = set(['a','e','i','o','u','A','E','I','O','U'])
    pointer_one = 0
    pointer_two = len(s)-1
    count_one, count_two = 0, 0
    while pointer_one < pointer_two:
         if s[pointer_one] in vowel_str:
            count_one += 1
         pointer_one +=1
         if s[pointer_two] in vowel_str:
            count_two += 1
         pointer_two -= 1
    return count_one - count_two == 0

Time and Space complexity

We are using a set so there's our O(n) space complexity albeit it should actually be O(10) complexity since the extra spae is constant

Since we need to iterate over the string the time complexity is O(n) where n is the length of the string. In reality, the comparison with the set should also be taken into account but since we are using a set the comparison is fairly fast and so I have chosen to negelect the time it takes to do so.

That's all folks! Feel free to share your approaches to the problem as well.