Determine if String Halves Are Alike

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.

We can iterate the first half of the s and consider it as a, and similarly, iterate the second half of the s, and consider it as b. And can count the number of vowels in each of the halves.

Algorithm

Step 1: Iterate over the first half of s (i.e., a) and the second half of s (i.e., b). Count the number of vowels respectively.

Step 2: Return if the numbers of vowels equal.

class Solution {
    public boolean halvesAreAlike(String s) {
        
        int n = s.length();

        String vowels = "aeiouAEIOU";

        int first_half_vowel_count = 0;
        for (int i = 0; i < n / 2; i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) {
                first_half_vowel_count++;
            }
        }

        int second_half_vowel_count = 0;
        for (int i = n / 2; i < n; i++) {
            if (vowels.indexOf(s.charAt(i)) != -1) {
                second_half_vowel_count++;
            }
        }

        return first_half_vowel_count == second_half_vowel_count;
    }
}

Complexity Analysis

Let N be the length of s.

  • Time Complexity: O(N), since we need to iterate substring a and b.
  • Space Complexity: O(1), since we do not need extra space. Here we do not take the input s into consideration.

Categories: String

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s