algoadvance

Leetcode 1704. Determine if String Halves Are Alike

Problem Statement

  1. 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 determine if these halves are alike.

Two strings are considered 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 the two halves of the string are alike; otherwise, return false.

Example

Constraints

Clarifying Questions

  1. Should only English alphabets be considered, and no special characters or numbers?
    • Yes, the string consists of uppercase and lowercase English letters only.
  2. Would the string always be of even length as mentioned in the constraints?
    • Yes, the string s will always have an even length.

Strategy

  1. Identify Vowels: Create a set of characters representing the vowels (both uppercase and lowercase).
  2. Split the String: Split the string s into two halves.
  3. Count Vowels: Count the number of vowels in both halves of the string.
  4. Compare the Counts: Compare the vowel counts of the two halves.
  5. Return Result: Return true if the counts are equal, otherwise return false.

Code

#include <iostream>
#include <unordered_set>
#include <cctype>

bool halvesAreAlike(std::string s) {
    std::unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
    
    int n = s.length();
    int half = n / 2;
    int count1 = 0, count2 = 0;
    
    for (int i = 0; i < half; ++i) {
        if (vowels.count(s[i])) ++count1;
        if (vowels.count(s[half + i])) ++count2;
    }
    
    return count1 == count2;
}

int main() {
    std::string s1 = "book";
    std::string s2 = "text";
    std::cout << std::boolalpha << halvesAreAlike(s1) << std::endl;  // Output: true
    std::cout << std::boolalpha << halvesAreAlike(s2) << std::endl;  // Output: false
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string. This is because we need to iterate through each character of the string once.

The space complexity is O(1) because we’re using only a constant amount of extra space (for the set of vowels and a few integer counters).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI