Leetcode – Determine if String Halves Are Alike Solution

Spread the love

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.

Problem Statement

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.

Example

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.

Python Code

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

Time Complexity

This approach has a time complexity of O(n), where n is the length of the string s.

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.

Python Code

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

Time Complexity

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

Conclusion

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.

Leave a Reply