algoadvance

Leetcode 1704. Determine if String Halves Are Alike

Problem Statement:

This problem is from LeetCode and is labeled “1704. Determine if String Halves Are Alike.” The problem statement is as follows:

You are given a string s of even length. Split this string into two halves of equal lengths. The first half is a and the second half is b. Two strings a and b are alike if they have the same number of vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘A’, ‘E’, ‘I’, ‘O’, ‘U’). Note that a vowel is the same in uppercase and lowercase.

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, but b has 2. Therefore, they are not alike.

Clarifying Questions:

1. Is the length of string s guaranteed to be even?
   • Yes, per the problem statement.
2. Are we considering only vowels as defined by the problem (a, e, i, o, u in both cases)?
   • Yes, only those characters.

Strategy:

1. Split the string s into two halves: a and b.
2. Define a helper function to count the number of vowels in a given substring.
3. Compare the number of vowels in both halves and return true if they are the same, else return false.

Code:

import java.util.HashSet;
import java.util.Set;

public class DetermineStringHalvesAlike {
    // Set containing vowels for quick lookup
    private static final Set<Character> VOWELS = new HashSet<>();
    
    static {
        VOWELS.add('a'); VOWELS.add('e'); VOWELS.add('i'); VOWELS.add('o'); VOWELS.add('u');
        VOWELS.add('A'); VOWELS.add('E'); VOWELS.add('I'); VOWELS.add('O'); VOWELS.add('U');
    }

    public boolean halvesAreAlike(String s) {
        int n = s.length();
        int mid = n / 2;
        
        int firstHalfVowelCount = countVowels(s, 0, mid);
        int secondHalfVowelCount = countVowels(s, mid, n);
        
        return firstHalfVowelCount == secondHalfVowelCount;
    }

    private int countVowels(String s, int start, int end) {
        int count = 0;
        for (int i = start; i < end; i++) {
            if (VOWELS.contains(s.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        DetermineStringHalvesAlike solution = new DetermineStringHalvesAlike();

        // Example 1
        System.out.println(solution.halvesAreAlike("book"));  // Output: true

        // Example 2
        System.out.println(solution.halvesAreAlike("textbook"));  // Output: false
    }
}

Time Complexity:

• O(n): The string is traversed twice, once to split into halves and then to count vowels, making it linear in time complexity with respect to the length of the string s.

This approach ensures efficient and clear comparison between the two halves of the string to determine if they are alike based on the count of vowels.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?