1704. Determine if String Halves Are Alike

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.

Solutions

Solution 1: Counting

Traverse the string. If the number of vowels in the first half of the string is equal to the number of vowels in the second half, return true. Otherwise, return false.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(C)$, where $C$ is the number of vowel characters.

Python Code
1
2
3
4
5
6
7
8

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

Java Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

Go Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func halvesAreAlike(s string) bool {
	vowels := map[byte]bool{}
	for _, c := range "aeiouAEIOU" {
		vowels[byte(c)] = true
	}
	cnt, n := 0, len(s)>>1
	for i := 0; i < n; i++ {
		if vowels[s[i]] {
			cnt++
		}
		if vowels[s[i+n]] {
			cnt--
		}
	}
	return cnt == 0
}

TypeScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

function halvesAreAlike(s: string): boolean {
    const set = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
    const n = s.length >> 1;
    let count = 0;
    for (let i = 0; i < n; i++) {
        set.has(s[i]) && count++;
        set.has(s[n + i]) && count--;
    }
    return count === 0;
}

Rust Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashSet;
impl Solution {
    pub fn halves_are_alike(s: String) -> bool {
        let set: HashSet<&u8> = [b'a', b'e', b'i', b'o', b'u', b'A', b'E', b'I', b'O', b'U']
            .into_iter()
            .collect();
        let s = s.as_bytes();
        let n = s.len() >> 1;
        let mut count = 0;
        for i in 0..n {
            if set.contains(&s[i]) {
                count += 1;
            }
            if set.contains(&s[n + i]) {
                count -= 1;
            }
        }
        count == 0
    }
}

JavaScript Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/**
 * @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;
};

PHP Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    /**
     * @param String $s
     * @return Boolean
     */
    function halvesAreAlike($s) {
        $cnt = 0;
        for ($i = 0; $i < strlen($s) / 2; $i++) {
            if (strpos('aeiouAEIOU', $s[$i]) !== false) {
                $cnt++;
            }
            if (strpos('aeiouAEIOU', $s[strlen($s) / 2 + $i]) !== false) {
                $cnt--;
            }
        }
        return $cnt == 0;
    }
}

Solution 2

Python Code
1
2
3
4
5

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set('aeiouAEIOU')
        a, b = s[: len(s) >> 1], s[len(s) >> 1 :]
        return sum(c in vowels for c in a) == sum(c in vowels for c in b)