Jobs

Interviews

Discussions

Determine if String Halves Are Alike

Easy

Asked by:

36 views

Topics:

Strings

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 <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Try coding it in LeetCode

Determine if String Halves Are Alike

Easy

Asked by:

36 views

Topics:

Strings

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 <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to have an even length?
Is the input string case-sensitive? Should I consider 'A' and 'a' as the same vowel?
What characters can appear in the string, besides vowels? Are there only letters, or can there be spaces, numbers, or other special characters?
By 'alike', do you mean the halves must contain the same *number* of vowels, regardless of which vowels are present?
Should I consider 'y' a vowel?

Brute Force Solution

Approach

The brute force strategy for this problem is pretty straightforward: We'll check all possible combinations of vowels in the first half of the string and compare it against all possible combinations of vowels in the second half. This is done by directly counting the vowels in each half and then comparing the counts.

Here's how the algorithm would work step-by-step:

First, split the given string into two equal halves.
Next, for the first half, count the number of vowels (a, e, i, o, u). Remember to treat both uppercase and lowercase vowels as the same.
Then, do the same vowel count for the second half of the string.
Finally, compare the vowel counts of the first and second halves. If the counts are the same, then the two halves are alike.

Code Implementation

def halves_are_alike(string_to_check: str) -> bool:
    string_length = len(string_to_check)
    middle_index = string_length // 2

    first_half = string_to_check[:middle_index]
    second_half = string_to_check[middle_index:]

    # Initialize counters for each half.
    first_half_vowel_count = 0
    second_half_vowel_count = 0

    vowels = "aeiouAEIOU"

    # Iterate to count vowels in first half
    for char in first_half:

        #Check if this character is a vowel. 
        if char in vowels:

            first_half_vowel_count += 1

    # Iterate to count vowels in second half
    for char in second_half:

        # Check if this character is a vowel.
        if char in vowels:

            second_half_vowel_count += 1

    # Compare vowel counts and return if halves are alike.
    return first_half_vowel_count == second_half_vowel_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the first half of the string to count vowels, which takes O(n/2) time, where n is the length of the string. Similarly, it iterates through the second half of the string to count vowels, also taking O(n/2) time. Finally, it compares the two vowel counts in O(1) time. Thus, the overall time complexity is O(n/2) + O(n/2) + O(1), which simplifies to O(n).

Space Complexity

O(1) – The algorithm calculates vowel counts for the two halves of the string using a fixed number of integer variables. No auxiliary data structures that scale with the input size N (the length of the string) are used. Therefore, the space complexity is constant, regardless of the input string's length.

Optimal Solution

Approach

The goal is to quickly check if the first half and second half of a string have the same number of vowels. Instead of doing extra work, we will focus on counting vowels efficiently and comparing the counts.

Here's how the algorithm would work step-by-step:

First, find the middle point of the string.
Then, count the number of vowels in the first half of the string.
Next, count the number of vowels in the second half of the string.
Finally, compare the two vowel counts. If they are the same, the string halves are alike.

Code Implementation

def halves_are_alike(input_string):
    string_length = len(input_string)
    middle_index = string_length // 2

    first_half = input_string[:middle_index]
    second_half = input_string[middle_index:]

    # We define vowels to make it easy to check
    vowels = "aeiouAEIOU"

    first_half_vowel_count = 0
    for char in first_half:
        if char in vowels:
            first_half_vowel_count += 1

    second_half_vowel_count = 0
    for char in second_half:
        if char in vowels:
            second_half_vowel_count += 1

    # Return True if vowel counts are equal
    if first_half_vowel_count == second_half_vowel_count:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the first half of the string to count vowels, which takes n/2 operations where n is the length of the string. Similarly, it iterates through the second half of the string counting vowels which also takes n/2 operations. Finally, a single comparison is performed. Therefore, the number of operations approximates n/2 + n/2 + 1, which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the middle point and vowel counts for both halves of the string. The number of variables does not depend on the string's length (N). Therefore, the auxiliary space required is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately, as both halves have zero vowels.
String with odd length	Return false immediately, as halves must have equal lengths.
String with only consonants	Return true, as both halves will have zero vowels.
String with only vowels	Compare the counts directly to check for equality.
Very long input string	The algorithm should have O(n) time complexity, so scaling isn't a major issue, but memory usage should be considered for extremely large strings.
String with mixed case vowels (a vs A)	Convert the entire string to lowercase or uppercase before counting vowels.
String with maximum length containing only vowels in one half	Ensure counter does not overflow and the processing is efficient.
String with maximum length containing only consonants	This case should not cause problems if the solution uses O(1) memory for vowel counting and O(n) processing time.

Null or empty string input

How to Handle:

Return true immediately, as both halves have zero vowels.

String with odd length

How to Handle:

Return false immediately, as halves must have equal lengths.

String with only consonants

How to Handle:

Return true, as both halves will have zero vowels.

String with only vowels

How to Handle:

Compare the counts directly to check for equality.

Very long input string

How to Handle:

The algorithm should have O(n) time complexity, so scaling isn't a major issue, but memory usage should be considered for extremely large strings.

String with mixed case vowels (a vs A)

How to Handle:

Convert the entire string to lowercase or uppercase before counting vowels.

String with maximum length containing only vowels in one half

How to Handle:

Ensure counter does not overflow and the processing is efficient.

String with maximum length containing only consonants

How to Handle:

This case should not cause problems if the solution uses O(1) memory for vowel counting and O(n) processing time.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string guaranteed to have an even length?
Is the input string case-sensitive? Should I consider 'A' and 'a' as the same vowel?
What characters can appear in the string, besides vowels? Are there only letters, or can there be spaces, numbers, or other special characters?
By 'alike', do you mean the halves must contain the same *number* of vowels, regardless of which vowels are present?
Should I consider 'y' a vowel?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, split the given string into two equal halves.
Next, for the first half, count the number of vowels (a, e, i, o, u). Remember to treat both uppercase and lowercase vowels as the same.
Then, do the same vowel count for the second half of the string.
Finally, compare the vowel counts of the first and second halves. If the counts are the same, then the two halves are alike.

Code Implementation

def halves_are_alike(string_to_check: str) -> bool:
    string_length = len(string_to_check)
    middle_index = string_length // 2

    first_half = string_to_check[:middle_index]
    second_half = string_to_check[middle_index:]

    # Initialize counters for each half.
    first_half_vowel_count = 0
    second_half_vowel_count = 0

    vowels = "aeiouAEIOU"

    # Iterate to count vowels in first half
    for char in first_half:

        #Check if this character is a vowel. 
        if char in vowels:

            first_half_vowel_count += 1

    # Iterate to count vowels in second half
    for char in second_half:

        # Check if this character is a vowel.
        if char in vowels:

            second_half_vowel_count += 1

    # Compare vowel counts and return if halves are alike.
    return first_half_vowel_count == second_half_vowel_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the middle point of the string.
Then, count the number of vowels in the first half of the string.
Next, count the number of vowels in the second half of the string.
Finally, compare the two vowel counts. If they are the same, the string halves are alike.

Code Implementation

def halves_are_alike(input_string):
    string_length = len(input_string)
    middle_index = string_length // 2

    first_half = input_string[:middle_index]
    second_half = input_string[middle_index:]

    # We define vowels to make it easy to check
    vowels = "aeiouAEIOU"

    first_half_vowel_count = 0
    for char in first_half:
        if char in vowels:
            first_half_vowel_count += 1

    second_half_vowel_count = 0
    for char in second_half:
        if char in vowels:
            second_half_vowel_count += 1

    # Return True if vowel counts are equal
    if first_half_vowel_count == second_half_vowel_count:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately, as both halves have zero vowels.
String with odd length	Return false immediately, as halves must have equal lengths.
String with only consonants	Return true, as both halves will have zero vowels.
String with only vowels	Compare the counts directly to check for equality.
Very long input string	The algorithm should have O(n) time complexity, so scaling isn't a major issue, but memory usage should be considered for extremely large strings.
String with mixed case vowels (a vs A)	Convert the entire string to lowercase or uppercase before counting vowels.
String with maximum length containing only vowels in one half	Ensure counter does not overflow and the processing is efficient.
String with maximum length containing only consonants	This case should not cause problems if the solution uses O(1) memory for vowel counting and O(n) processing time.

Null or empty string input

How to Handle:

Return true immediately, as both halves have zero vowels.

String with odd length

How to Handle:

Return false immediately, as halves must have equal lengths.

String with only consonants

How to Handle:

Return true, as both halves will have zero vowels.

String with only vowels

How to Handle:

Compare the counts directly to check for equality.

Very long input string

How to Handle:

The algorithm should have O(n) time complexity, so scaling isn't a major issue, but memory usage should be considered for extremely large strings.

String with mixed case vowels (a vs A)

How to Handle:

Convert the entire string to lowercase or uppercase before counting vowels.

String with maximum length containing only vowels in one half

How to Handle:

Ensure counter does not overflow and the processing is efficient.

String with maximum length containing only consonants

How to Handle:

This case should not cause problems if the solution uses O(1) memory for vowel counting and O(n) processing time.