Algorithm to Determine if String Halves Are Alike (Same Number of Vowels)

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.

Example 3:
Input: s = “MerryChristmas”
Output: false

Example 4:
Input: s = “AbCdEfGh”
Output: true

Constraints:
2 <= s.length <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Hints:
Create a function that checks if a character is a vowel, either uppercase or lowercase.

C++ Number of Vowels for a String

As it describes, we need to check the number of the vowels for each half of the string, and return true if it is equal. Thus, we can do this in O(N) time. We can define a local function that does so. The vowels are feeded into a unordered hash set so that we can check if current character (while we iterate the string) in O(1) lookup time.

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

class Solution {
public:
    bool halvesAreAlike(string s) {
        int n = s.size() / 2;
        string a = s.substr(0, n);
        string b = s.substr(n);
        function<int(string &s)> numberOfVowels = [](string &a) {
            unordered_set<char> vs({'a', 'e', 'i', 'o', 'u'});
            int ans = 0;
            for (auto &n: a) {
                ans += vs.count(tolower(n));
            }
            return ans;
        };
        return numberOfVowels(a) == numberOfVowels(b);
    }
};

class Solution {
public:
    bool halvesAreAlike(string s) {
        int n = s.size() / 2;
        string a = s.substr(0, n);
        string b = s.substr(n);
        function<int(string &s)> numberOfVowels = [](string &a) {
            unordered_set<char> vs({'a', 'e', 'i', 'o', 'u'});
            int ans = 0;
            for (auto &n: a) {
                ans += vs.count(tolower(n));
            }
            return ans;
        };
        return numberOfVowels(a) == numberOfVowels(b);
    }
};

–EOF (The Ultimate Computing & Technology Blog)