Strings are a fundamental data type in programming, and they come up frequently in both interviews and real-world applications. The “Determine if String Halves Are Alike” problem on Leetcode is an excellent example of a string problem that tests your understanding of string manipulation, conditional statements, and loops. In this comprehensive guide, we’ll walk through different approaches to solving the problem, their time and space complexities, and ways to optimize your code further.
Given a string
s, split it in half and determine if both halves are “alike.” A string half is considered “alike” if it has the same number of vowels (
'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). It is guaranteed that
s will have even length.
Input: s = "book" Output: True
Naive Approach: Iterating through both halves
The most straightforward approach is to iterate through both halves of the string, count the number of vowels in each half, and then compare the counts.
def halvesAreAlike(s): vowels = set("aeiouAEIOU") first_half = s[:len(s) // 2] second_half = s[len(s) // 2:] first_count = sum(1 for char in first_half if char in vowels) second_count = sum(1 for char in second_half if char in vowels) return first_count == second_count
This approach has a time complexity of O(n), where n is the length of the string
Optimized Approach: Single Loop
Instead of iterating twice through both halves, you can iterate once while maintaining two separate counters for the first and second halves.
def halvesAreAlike(s): vowels = set("aeiouAEIOU") count = 0 n = len(s) // 2 for i in range(n): if s[i] in vowels: count += 1 if s[i + n] in vowels: count -= 1 return count == 0
The time complexity remains O(n), but this approach reduces the number of iterations through the string.
Testing Your Solution
Before you submit your solution, make sure to test it against some custom and edge cases to verify its correctness.
assert halvesAreAlike("book") == True assert halvesAreAlike("textbook") == False assert halvesAreAlike("AbCd") == True assert halvesAreAlike("MnOp") == False
The “Determine if String Halves Are Alike” problem provides a valuable opportunity to exercise your skills in string manipulation and conditional logic. It also offers insights into how you can optimize your code to be more efficient both in terms of time and readability. Even though the problem may seem straightforward, the optimization strategies and considerations for edge cases make it an interesting one.