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.
Example 1:
Input: s = "book" Output: true Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.
Example 2:
Input: s = "textbook" Output: false Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike. Notice that the vowel o is counted twice.
Constraints:
2 <= s.length <= 1000s.length is even.s consists of uppercase and lowercase letters.In #1704 Determine if String Halves Are Alike, the goal is to check whether the two halves of a string contain the same number of vowels. Since the string length is always even, you can split it into two equal parts and compare their vowel counts.
A common approach is to maintain a vowel lookup set such as {a, e, i, o, u} including uppercase variants. Traverse the string while counting vowels in the first half and second half. Instead of storing both counts separately, you can also keep a single counter—increment when encountering a vowel in the first half and decrement when encountering one in the second half.
If the final counter is 0, both halves have the same number of vowels and are considered alike. This approach requires only a single pass through the string, making it efficient with O(n) time and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass vowel counting | O(n) | O(1) |
| Two counters for each half | O(n) | O(1) |
Algorithms Made Easy
Use these hints if you're stuck. Try solving on your own first.
Create a function that checks if a character is a vowel, either uppercase or lowercase.
This method involves using two pointers to count the number of vowels in each half of the string.
By using a set to identify vowels, iterate through each character in both halves. Compare the final counts for equality to determine if they are alike.
Time Complexity: O(n), where n is the length of the string, as we iterate through the string once.
Space Complexity: O(1), since we use only a fixed amount of extra space.
1function halvesAreAlike(s) {
2 const vowels = new Set('aeiouAEIOU');
3 const half = s.length / 2;
4 This JavaScript code leverages a Set to hold vowel characters, enabling fast lookup. The solution involves scanning each half of the string for vowels and then determining if the two halves have an equal number of vowels.
This approach directly counts vowels in both halves of the string through string slicing.
Both halves of the string are iterated efficiently with a loop, accumulating vowel counts independently. The results are directly compared to ensure both halves are alike.
Time Complexity: O(n) - single pass counts vowels for two halves.
Space Complexity: O(1) - constant time storage allocation.
#include <unordered_set>
using namespace std;
bool halvesAreAlike(string s) {
unordered_set<char> vowels{'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int length = s.size();
int half = length / 2;
int vowelCounts[2] = {0};
for (int i = 0; i < half; i++) {
if (vowels.count(s[i])) vowelCounts[0]++;
if (vowels.count(s[i + half])) vowelCounts[1]++;
}
return vowelCounts[0] == vowelCounts[1];
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Store all vowels (both lowercase and uppercase) in a set for O(1) lookup. During traversal, simply check whether the current character exists in the set and update the vowel counter accordingly.
This problem is categorized as easy but tests basic string traversal and counting logic. While it may not be a core FAANG interview question, similar string manipulation and counting patterns appear frequently in technical interviews.
A hash set or lookup set is commonly used to store vowels for quick membership checks. This allows constant-time verification when scanning each character of the string.
The optimal approach is to count vowels in both halves of the string using a single traversal. You can increment a counter for vowels in the first half and decrement it for vowels in the second half. If the final value is zero, both halves contain the same number of vowels.
This C++ solution uses arrays to simultaneously gather vowel counts from both string halves. Dual storage allows localized processing, negating the need for additional refinement passes and maintains sublinear complexity.