Determine if String Halves Are Alike - Solution & Explanation
Problem 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.
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.lengthis even.sconsists of uppercase and lowercase letters.
Approach Overview
Problem Overview: You receive a string s with even length. Split it into two halves and determine whether both halves contain the same number of vowels. Vowels include a, e, i, o, u in both lowercase and uppercase. The task reduces to counting vowels in each half and comparing the totals.
Approach 1: Character Counting via Direct Comparison (O(n) time, O(1) space)
Traverse the string and count vowels separately for the first and second halves. Compute the midpoint using mid = n / 2, then iterate from 0 → mid-1 to count vowels in the first half and from mid → n-1 for the second half. Each character is checked against a small set of vowels using direct comparison or membership lookup. Since the vowel set is constant in size, every check runs in constant time, giving a total time complexity of O(n) and constant auxiliary space O(1). This approach is simple and very readable, making it ideal when clarity matters more than minimizing passes.
Approach 2: Two-Pointer Vowel Count Approach (O(n) time, O(1) space)
Use two pointers that move through the two halves simultaneously. One pointer starts at the beginning of the string, and the other starts at the midpoint. On each iteration, check whether each pointer points to a vowel and update two counters (or maintain a single difference counter). This processes both halves in a single loop while performing constant-time vowel checks using a predefined set like "aeiouAEIOU". The algorithm still scans each character once, so the time complexity remains O(n) with O(1) extra space. The advantage is fewer loops and a symmetric structure that mirrors the two halves being compared.
Both strategies rely on fundamental string traversal and simple counting logic. No additional data structures are required because the problem only tracks a small number of counters and checks membership in a constant-size vowel set.
Recommended for interviews: The two-pointer vowel counting approach is typically preferred. It demonstrates clean iteration logic and efficient comparison of both halves in a single pass. Showing the direct counting version first can communicate your understanding quickly, while the two-pointer refinement shows awareness of cleaner traversal patterns often expected in string problems.
Approach 1: Two-Pointer Vowel Count Approach
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.
This C solution uses a helper function isVowel to check if a character is a vowel. We loop through the first half of the string and the corresponding second half to count vowels and compare their counts.
Complexity
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.
Approach 2: Character Counting via Direct Comparison
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.
This C variant maintains a dual integer array to count the vowels from both halves of the input string. This array allows simultaneous count validation during traversal, guaranteeing optimal time use without auxiliary data structures.
Complexity
Time Complexity: O(n) - single pass counts vowels for two halves.
Space Complexity: O(1) - constant time storage allocation.
Approach 3: Counting
Traverse the string. If the number of vowels in the first half of the string is equal to the number of vowels in the second half, return true. Otherwise, return false.
The time complexity is O(n), where n is the length of the string. The space complexity is O(C), where C is the number of vowel characters.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Vowel Count Approach | 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. |
| Character Counting via Direct Comparison | Time Complexity: O(n) - single pass counts vowels for two halves. Space Complexity: O(1) - constant time storage allocation. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Counting via Direct Comparison | O(n) | O(1) | When clarity and straightforward logic are preferred; good baseline solution |
| Two-Pointer Vowel Count Approach | O(n) | O(1) | When comparing two segments simultaneously with cleaner single-pass traversal |
Video Solution
Determine if String Halves Are Alike | Live Coding with Explanation | Leetcode - 1704 • Algorithms Made Easy • 2,363 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Determine if String Halves Are Alike easy or hard?
Determine if String Halves Are Alike Python/Java solution
How to solve Determine if String Halves Are Alike in O(n)?
What is the best approach for Determine if String Halves Are Alike?
Is Determine if String Halves Are Alike asked at Google/Amazon/Meta?
What data structure is used in Determine if String Halves Are Alike?
What is the time complexity of Determine if String Halves Are Alike?
Ready to solve this problem?
Practice Determine if String Halves Are Alike with our built-in code editor and test cases.
Practice on FleetCode