Determining if String Halves are Alike: Using the Frequency Counter Approach
A walkthrough on how to determine if both strings contain the same number of vowels using the Frequency Counter approach in JavaScript
Let’s get right into it, shall we?
Note that this problem is on Leetcode (question #1704). To follow along, the link to the question is as follows: https://leetcode.com/problems/determine-if-string-halves-are-alike/
The Problem
Our problem states:
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.
OK — so we have a few things to consider. First, we need to take our input string and split it in half. The input string is of even length, so we can be sure that our split strings will also be of even length.
Next, we have to consider both lowercase & uppercase vowels. We’ll have to account for this when creating our array.
Lastly, we’ll have to keep track of the number of vowels we encounter in each string. We’ll have to use this to compare whether the strings are alike. Remember, strings are alike if they contain the same number of vowels.
The Approach
Before diving into the solution, let’s take our typical approach & lay out the groundwork so we’re clear as to the steps we need to take.
- Split our string into equal halves. We can use the built-in string method substring to accomplish this and set both strings to a variable
The substring method takes in two arguments; the first argument is the index of where we want to start the subsequence, while the second argument is where we want to end the subsequence.
2. Create our vowels array which we’ll use to check whether the strings contain a uppercase or lowercase vowel.
3. Initialize two empty hashes which will store the frequency count of each element in their two respective strings
4. Initialize two variables that will hold the total number of vowels in their respective string. We’ll use these counters to determine the output of our function
5. Loop through both of our strings -> set our keys to the character and our values as the number of times they appear in the string
6. Set a outer loop that will loop through the keys of both of our hashes -> we’ll set a inner loop that will loop over our vowels array, checking to see if the key matches any of the values in the vowels array. This will give us the total number of vowels in both string, which we will use to determine whether the strings are alike.
The Solution
Now that we have our roadmap planned, let’s write some code!
Let’s assume our test case is the string, “book” We should expect that we return true as “bo” and “ok” both contains one vowel.
Our first steps are to initialize our variables. Remember, we need to split our string into halves, create an array that holds our vowels in both uppercase & lowercase, create two empty hashes that will hold our frequency counters, and two counter variables. That’s a lot of variables!
Notice in our substring arguments, in order to get the halfway point of our strings, we do a simple math operation and divide the length of our string by 2.
As you can see in our console log, our substrings are split in equal lengths, splitting our 4 character string into two 2 character strings.
Next, we need to populate our hashes and count the frequency of each character in their respective string. We can use two for loops to achieve this step:
As we can see in our console log, our hashes contain the frequency count of our characters. As expected, we have 1 count of “b” and “o” for our first string, and 1 count of “o” and “k” for our second string.
Lastly, we need to iterate over the keys of our hashes and check whether they’re a vowel. We do this by setting up a nested for loop that will iterate over our vowels array. With each iteration that encounters a match, we’ll increase our halfA and halfB counts by the value (or count) of the vowel.
At the end of our function, we’ll compare the values of halfA and halfB, returning true if they are equal (meaning our strings are alike) and false if they are not.
Conclusion
While this approach is certainly long-winded (and not very efficient as its in quadratic time), I hope it was clear enough for you to follow each step of the way.
By creating an array that contains all of our vowels, both uppercase & lowercase, we can use it to lookup whether the strings contain any vowels & how many. In addition, using the frequency counter approach allows us to count the number of times each vowel appears, and add that value to our total so we can easily compare our halfA & halfB totals to determine whether our two substrings are alike or not.
Please feel free to comment below with any questions or suggestions or if you have a more efficient approach on this problem.
Until next time!
