Determine if String Halves Are Alike

EASY

Description

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.

Approaches

Checkout 3 different approaches to solve Determine if String Halves Are Alike. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Substring Creation

This approach involves splitting the input string into two separate substrings representing the first and second halves. Then, it counts the vowels in each substring independently and compares the counts.

Algorithm

Calculate the middle index: mid = s.length() / 2.
Create the first half substring a from index 0 to mid.
Create the second half substring b from index mid to the end.
Define a helper function countVowels(String str):
- Initialize a vowel counter to 0.
- Define a string containing all vowels: "aeiouAEIOU".
- Iterate through each character of the input string str.
- If the character is found in the vowels string, increment the counter.
- Return the final count.
Call countVowels for both a and b.
Return true if the counts are equal, false otherwise.

The core idea is to first divide the problem into two smaller, identical subproblems: counting vowels in a string. First, we calculate the middle index of the string s. Using the substring method, we create two new strings: a for the first half (from index 0 to mid-1) and b for the second half (from index mid to the end). We then iterate through each of these new substrings. For each character, we check if it's a vowel. A simple way to check for a vowel is to see if the character exists in a predefined string of all vowels ("aeiouAEIOU"). We maintain two separate counters, one for each half. After iterating through both substrings, we compare the final counts. If they are equal, the halves are alike; otherwise, they are not.

class Solution {
    public boolean halvesAreAlike(String s) {
        int mid = s.length() / 2;
        String a = s.substring(0, mid);
        String b = s.substring(mid);
        
        return countVowels(a) == countVowels(b);
    }

    private int countVowels(String str) {
        int count = 0;
        String vowels = "aeiouAEIOU";
        for (char c : str.toCharArray()) {
            if (vowels.indexOf(c) != -1) {
                count++;
            }
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string `s`. Creating substrings takes O(N) time. The `countVowels` function also iterates through N/2 characters for each half, resulting in a total of O(N) operations. The `indexOf` check on a small, constant-size string is effectively O(1).Space Complexity: O(N), where N is the length of the string `s`. This is because creating two substrings of length N/2 requires allocating new memory proportional to the length of the original string.

Pros and Cons

Pros:

The logic is very clear and easy to follow.
It modularizes the problem well by using a helper function for counting vowels.

Cons:

It's not space-efficient. Creating new substrings consumes O(N) extra memory, which is unnecessary.

Code Solutions

Checking out 4 solutions in different languages for Determine if String Halves Are Alike. Click on different languages to view the code.

class Solution {
private
  static final Set<Character> VOWELS =
      Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
public
  boolean halvesAreAlike(String s) {
    int cnt = 0, n = s.length() >> 1;
    for (int i = 0; i < n; ++i) {
      cnt += VOWELS.contains(s.charAt(i)) ? 1 : 0;
      cnt -= VOWELS.contains(s.charAt(i + n)) ? 1 : 0;
    }
    return cnt == 0;
  }
}

Video Solution

Watch the video walkthrough for Determine if String Halves Are Alike

Patterns:

Counting

Data Structures:

String