1704. Determine if String Halves Are Alike

EasyStringCounting
Leetcode Link

Problem Description

In this problem, you are given a string s with an even number of characters. Your task is to divide the string into two equal parts: a which is the first half, and b which is the second half of the string s. After the split, you must determine whether the two strings are "alike." Two strings are considered alike if they contain the same number of vowels. Vowels are the characters 'a', 'e', 'i', 'o', and 'u' in both lowercase and uppercase forms. You need to return true if the substrings a and b are alike (i.e., have the same number of vowels). Otherwise, return false.

Intuition

To solve this problem, you need to count the number of vowels in both halves of the string and compare them. The most straightforward approach is to iterate through each half of the string separately, count the vowels in each half, and then compare the counts.

However, the provided solution takes a more efficient approach by calculating the difference in the number of vowels between both halves in a single pass. It uses a counter cnt that is incremented when a vowel is encountered in the first half and decremented when a vowel is found in the second half. By doing this, we combine the counting and comparison steps.

To check if a character is a vowel, the solution creates a set vowels containing all the vowels in both lowercase and uppercase. Using a set provides an efficient O(1) time complexity for checking if an element is present.

The variable n represents half the length of the string. During the iteration, for each character in the first half (indexed by i), cnt is increased by 1 if it's a vowel. Correspondingly, for each character in the second half (indexed by i + n), cnt is decreased by 1 if it's a vowel.

If, after the single pass through the string, cnt is 0, this means the number of vowels in both halves are equal, and the two halves are alike (the function will return true). If cnt is not 0, there is a different number of vowels in each half (the function will return false).

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How many times is a tree node visited in a depth first search?

Solution Approach

The provided solution uses a counting approach combined with a set to efficiently check for vowels in each half of the string. Here's a detailed walkthrough of the algorithm and the data structures used:

  • Initialization:

    • A set vowels is created containing all vowel characters. This data structure is chosen because it allows for O(1) time complexity for vowel checks.
    • A variable cnt is initialized to 0. It represents the net difference in the number of vowels between the first half and the second half of the string.
    • The length of the first half of the string, denoted as n, is calculated using len(s) >> 1, which is equivalent to dividing the length of the string s by 2 using a bitwise right shift operator.

  • Iteration:

    • We loop through s from the start to the midpoint (range(n)). For each character in the first half:
      • We increment cnt if the character is found in the vowels set (indicating that it's a vowel).
    • Simultaneously, for the corresponding character in the second half (indexed by i + n):
      • We decrement cnt if this character is a vowel.

During this single loop over the string, the cnt variable effectively counts the number of vowels in the first half and subtracts the number of vowels in the second half. If the two halves contain an equal number of vowels, cnt will be 0 at the end of the loop:

  • Checking the result:
    • The cnt variable is compared to 0. If they are equal, it means that there were an equal number of vowels in both halves, and we return true.
    • If cnt is not 0, it indicates that the number of vowels in the two halves was different, and we return false.

This method is efficient because it traverses the string only once and performs the counting and comparison at the same time, which gives it a time complexity of O(n), where n is the length of the string. Additionally, since the solution requires a fixed amount of extra space for the vowel set and the counter, its space complexity is O(1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we are given the string s = "book".

  1. Initialization:

    • We create a set vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}.
    • We initialize cnt to 0.
    • Calculate half the length of the string n = len(s) >> 1 which is 2.

  2. Iteration:

    • As we loop through the first half of the string s, we have 'b' and 'o'.
      • 'b' is not in vowels, so cnt remains 0.
      • 'o' is in vowels, so we increment cnt by 1. Now cnt = 1.
    • For the second half of the string, the corresponding indices will be i + n = 2 and i + n = 3, which gives us 'o' and 'k'.
      • 'o' is in vowels, so we decrement cnt by 1. Now cnt returns to 0.
      • 'k' is not in vowels, so cnt remains 0.

  3. Checking the result:

    • After the iteration, cnt is 0.
    • Since cnt is 0, it indicates that both halves of the string contain the same number of vowels.
    • Therefore, we return true. The string "book" has equal numbers of vowels in both halves, making them alike.

In this example, the single pass counting of vowels in both halves efficiently concludes that the string halves are alike without the need for separate counts.

Solution Implementation

1class Solution:
2    def halvesAreAlike(self, s: str) -> bool:
3        # Initialize a count variable for tracking vowel balance and
4        # calculate the midpoint of the string.
5        vowel_count_balance, string_length_half = 0, len(s) // 2
6      
7        # Define a set containing all lowercase and uppercase vowels.
8        vowels = set('aeiouAEIOU')
9      
10        # Iterate through the first half of the string.
11        for i in range(string_length_half):
12            # If the character in the first half is a vowel, increment the balance counter.
13            vowel_count_balance += s[i] in vowels
14          
15            # If the corresponding character in the second half is a vowel, decrement the balance counter.
16            vowel_count_balance -= s[i + string_length_half] in vowels
17      
18        # If the balance counter is zero after the loop, both halves have the same number of vowels.
19        return vowel_count_balance == 0
20
1class Solution {
2    // Create a set that holds all the vowel characters (both lower and upper case)
3    private static final Set<Character> VOWELS = Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
4
5    /**
6     * This method checks if a string has equal number of vowels in both halves.
7     *
8     * @param s The input string to be checked.
9     * @return Returns true if both halves have the same number of vowels, false otherwise.
10     */
11    public boolean halvesAreAlike(String s) {
12        // Initialize a variable to keep the cumulative difference of vowels count
13        int vowelCountDifference = 0;
14        // n represents half the length of the input string, using bitwise right shift for division by 2
15        int n = s.length() >> 1;
16      
17        // Loop through each character of the first half and the corresponding character of the second half
18        for (int i = 0; i < n; ++i) {
19            // If the character at current position of first half is vowel, increment the difference count
20            vowelCountDifference += VOWELS.contains(s.charAt(i)) ? 1 : 0;
21            // If the character at the corresponding position in second half is vowel, decrement the difference count
22            vowelCountDifference -= VOWELS.contains(s.charAt(i + n)) ? 1 : 0;
23        }
24
25        // If vowelCountDifference is zero, it means both halves have the same number of vowels
26        return vowelCountDifference == 0;
27    }
28}
29
1#include <string>
2#include <unordered_set>
3using namespace std;
4
5class Solution {
6public:
7    bool halvesAreAlike(string s) {
8        // Define a set of vowels including both uppercase and lowercase.
9        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}; 
10      
11        // Initialize a counter to compare the number of vowels in each half.
12        int vowelBalance = 0;
13
14        // Calculate the midpoint of the string.
15        int midPoint = s.size() / 2;
16
17        // Loop to compare vowels in two halves of the string.
18        for (int i = 0; i < midPoint; ++i) {
19            // If the character in the first half is a vowel, increment the counter.
20            vowelBalance += vowels.count(s[i]);
21
22            // If the character in the second half is a vowel, decrement the counter.
23            vowelBalance -= vowels.count(s[i + midPoint]);
24        }
25
26        // The halves are alike if the vowelBalance is 0 (equal number of vowels).
27        return vowelBalance == 0;
28    }
29};
30
1// Function to check if two halves of a string contain the same number of vowels
2function halvesAreAlike(s: string): boolean {
3    // Define a set of vowels for quick lookup
4    const vowelsSet = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
5
6    // Calculate the half length of the string
7    const halfLength = s.length >> 1; // Equivalent to division by 2 using bitwise right shift
8
9    // Initialize a counter to compare vowel occurrences in both halves
10    let counter = 0;
11
12    // Loop through each character of the first half of the string
13    for (let i = 0; i < halfLength; i++) {
14        // If the character is a vowel, increment the counter
15        if (vowelsSet.has(s[i])) {
16            counter++;
17        }
18      
19        // Simultaneously check the corresponding character in the second half
20        // If it is a vowel, decrement the counter
21        if (vowelsSet.has(s[halfLength + i])) {
22            counter--;
23        }
24    }
25
26    // If the counter is zero, both halves have the same number of vowels
27    return counter === 0;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement recursion?

Time and Space Complexity

The given code snippet defines a function halvesAreAlike that checks if two halves of a string contain the same number of vowels.

Time Complexity:

To analyze the time complexity, we need to consider the operations that depend on the size of the input string s.

  • The length of the string s is determined with len(s), which is O(1).
  • The right shift operation len(s) >> 1 is also O(1).
  • Creating the vowels set is O(1) as it is initialized with a fixed number of characters.
  • The for loop runs n times, where n is half the length of the string. Inside the loop, we check the membership of s[i] and s[i + n] in the vowels set, and then update the cnt variable accordingly. The set membership checking is O(1) on average. Thus, the loop has a complexity of O(n).

Given that n is len(s) / 2, the time complexity of the entire function is dominated by the for loop, which gives us O(n/2). However, in big O notation, we drop constant factors, so the time complexity can be expressed as O(n) where n is the length of the string s.

Space Complexity:

  • The space complexity is determined by the additional space used by the algorithm independent of the input size.
  • The vowels set requires O(1) space because it contains a fixed number of vowels, which does not grow with the input.
  • The cnt variable also takes O(1) space.
  • The function does not use any data structures that grow with the input size.

Therefore, the space complexity of the function is O(1).

In conclusion, the time complexity is O(n) and the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫