# Determine if String Halves Are Alike
**Difficulty:** EASY
[External](https://leetcode.com/problems/determine-if-string-halves-are-alike)
Canonical: https://scaleengineer.com/dsa/problems/determine-if-string-halves-are-alike
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
---
## Problem
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
## 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.
**Time:** 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:** 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:** 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.
### Explanation
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.
```java
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;
    }
}
```
### 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.

## Two-Pass Iteration with Constant Space
This approach improves on the previous one by avoiding the creation of new substrings. It iterates through the original string in two separate passes—one for each half—to count the vowels, thus using only constant extra space.
**Time:** O(N), where N is the length of the string. We iterate through the entire string once (split across two loops). The `HashSet` creation is a constant time operation, and lookups are O(1) on average. · **Space:** O(1). The extra space used is for the `HashSet` of vowels, which has a constant size (10 characters), regardless of the input string's length.
**Pros:** Space-efficient, as it avoids creating new strings.; Maintains good readability.
**Cons:** Requires two separate loops to iterate over the string, which is slightly less elegant than a single-pass solution.
### Explanation
Instead of allocating memory for new substrings, we can work directly with the input string `s`. This eliminates the O(N) space overhead of the previous method.
We first establish a quick way to check for vowels. A `HashSet` containing all vowel characters (`'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'`) is ideal, as it provides an average time complexity of O(1) for lookups.
The algorithm then proceeds in two loops. The first loop iterates from the beginning of the string to the midpoint, counting vowels in the first half. The second loop iterates from the midpoint to the end of the string, counting vowels in the second half.
Finally, the two counts are compared to determine if the halves are alike.
```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean halvesAreAlike(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        int mid = s.length() / 2;
        int firstHalfCount = 0;
        int secondHalfCount = 0;

        // First pass: count vowels in the first half
        for (int i = 0; i < mid; i++) {
            if (vowels.contains(s.charAt(i))) {
                firstHalfCount++;
            }
        }

        // Second pass: count vowels in the second half
        for (int i = mid; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) {
                secondHalfCount++;
            }
        }

        return firstHalfCount == secondHalfCount;
    }
}
```
### Algorithm
- Create a `Set` of all vowel characters for O(1) lookup.
- Calculate the middle index: `mid = s.length() / 2`.
- Initialize two counters, `firstHalfCount` and `secondHalfCount`, to 0.
- Iterate from `i = 0` to `mid - 1`:
  - Get the character `s.charAt(i)`.
  - If the character is in the vowel set, increment `firstHalfCount`.
- Iterate from `i = mid` to `s.length() - 1`:
  - Get the character `s.charAt(i)`.
  - If the character is in the vowel set, increment `secondHalfCount`.
- Return `true` if `firstHalfCount` equals `secondHalfCount`, `false` otherwise.

## Optimal Single-Pass Solution
This is the most efficient approach. It uses a single loop to iterate through the first half of the string. In each iteration, it checks one character from the first half and its corresponding character from the second half, updating a single counter to track the difference in vowel counts.
**Time:** O(N), where N is the length of the string. The loop runs N/2 times, and in each iteration, we perform two character lookups and two hash set lookups. This results in a linear time complexity proportional to N. · **Space:** O(1). The extra space is constant, used only for the `HashSet` of vowels.
**Pros:** Most efficient in terms of both time and space.; Processes the string in a single pass, which can be slightly faster in practice due to better cache utilization and less loop overhead.; Elegant and concise code.
**Cons:** The logic of using a single difference counter might be slightly less intuitive for beginners compared to using two separate counters.
### Explanation
This method optimizes the process by combining the counting for both halves into a single loop. It iterates from the beginning of the string up to the midpoint.
A single counter, let's call it `vowelDifference`, is initialized to zero.
Inside the loop, for each index `i` in the first half, we examine `s.charAt(i)` and `s.charAt(i + mid)`, where `mid` is `s.length() / 2`.
If the character from the first half (`s.charAt(i)`) is a vowel, we increment `vowelDifference`.
If the character from the second half (`s.charAt(i + mid)`) is a vowel, we decrement `vowelDifference`.
After the loop completes, if `vowelDifference` is zero, it means the number of vowels added from the first half is perfectly balanced by the number of vowels subtracted from the second half. Therefore, the vowel counts are equal.
```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean halvesAreAlike(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        int mid = s.length() / 2;
        int vowelDifference = 0;

        for (int i = 0; i < mid; i++) {
            if (vowels.contains(s.charAt(i))) {
                vowelDifference++;
            }
            if (vowels.contains(s.charAt(i + mid))) {
                vowelDifference--;
            }
        }

        return vowelDifference == 0;
    }
}
```
### Algorithm
- Create a `Set` of all vowel characters for O(1) lookup.
- Calculate the middle index: `mid = s.length() / 2`.
- Initialize a counter `vowelDifference` to 0.
- Iterate with an index `i` from 0 to `mid - 1`:
  - Check if the character at `s.charAt(i)` (first half) is a vowel. If yes, increment `vowelDifference`.
  - Check if the character at `s.charAt(i + mid)` (second half) is a vowel. If yes, decrement `vowelDifference`.
- After the loop, return `true` if `vowelDifference` is 0, `false` otherwise.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {boolean} */ var halvesAreAlike = function ( s ) { const str = ' aeiouAEIOU ' ; let cnt = 0 ; for ( let i = 0 ; i < s . length / 2 ; i ++ ) { if ( str . indexOf ( s [ i ]) > - 1 ) cnt ++ ; if ( str . indexOf ( s [ s . length - 1 - i ]) > - 1 ) cnt -- ; } return cnt === 0 ; };
```

### CPP

```cpp
class Solution {
public:
  bool halvesAreAlike(string s) {
    unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u',
                                  'A', 'E', 'I', 'O', 'U'};
    int cnt = 0, n = s.size() / 2;
    for (int i = 0; i < n; ++i) {
      cnt += vowels.count(s[i]);
      cnt -= vowels.count(s[i + n]);
    }
    return cnt == 0;
  }
};

```

### Python

```python
class Solution:
    def halvesAreAlike(self, s: str) -> bool: cnt, n = 0, len(s) >> 1 vowels = set('aeiouAEIOU') for i in range(n): cnt += s[i] in vowels cnt -= s[i + n] in vowels return cnt == 0

```