Scale Engineer

Determine if String Halves Are Alike

Easy
#1562Time: O(N), where N is the length of the string `s`. Creating substrings takes O(N) time. The `countVowels` function also iterates through N/2 characters for each half, resulting in a total of O(N) operations. The `indexOf` check on a small, constant-size string is effectively O(1).Space: O(N), where N is the length of the string `s`. This is because creating two substrings of length N/2 requires allocating new memory proportional to the length of the original string.
Patterns
Counting
Data structures
String

Prompt

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.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves splitting the input string into two separate substrings representing the first and second halves. Then, it counts the vowels in each substring independently and compares the counts.

Algorithm

  • Calculate the middle index: mid = s.length() / 2.
  • Create the first half substring a from index 0 to mid.
  • Create the second half substring b from index mid to the end.
  • Define a helper function countVowels(String str):
    • Initialize a vowel counter to 0.
    • Define a string containing all vowels: "aeiouAEIOU".
    • Iterate through each character of the input string str.
    • If the character is found in the vowels string, increment the counter.
    • Return the final count.
  • Call countVowels for both a and b.
  • Return true if the counts are equal, false otherwise.

Walkthrough

The core idea is to first divide the problem into two smaller, identical subproblems: counting vowels in a string. First, we calculate the middle index of the string s. Using the substring method, we create two new strings: a for the first half (from index 0 to mid-1) and b for the second half (from index mid to the end). We then iterate through each of these new substrings. For each character, we check if it's a vowel. A simple way to check for a vowel is to see if the character exists in a predefined string of all vowels ("aeiouAEIOU"). We maintain two separate counters, one for each half. After iterating through both substrings, we compare the final counts. If they are equal, the halves are alike; otherwise, they are not.

class Solution {    public boolean halvesAreAlike(String s) {        int mid = s.length() / 2;        String a = s.substring(0, mid);        String b = s.substring(mid);                return countVowels(a) == countVowels(b);    }     private int countVowels(String str) {        int count = 0;        String vowels = "aeiouAEIOU";        for (char c : str.toCharArray()) {            if (vowels.indexOf(c) != -1) {                count++;            }        }        return count;    }}

Complexity

Time

O(N), where N is the length of the string `s`. Creating substrings takes O(N) time. The `countVowels` function also iterates through N/2 characters for each half, resulting in a total of O(N) operations. The `indexOf` check on a small, constant-size string is effectively O(1).

Space

O(N), where N is the length of the string `s`. This is because creating two substrings of length N/2 requires allocating new memory proportional to the length of the original string.

Trade-offs

Pros

  • The logic is very clear and easy to follow.

  • It modularizes the problem well by using a helper function for counting vowels.

Cons

  • It's not space-efficient. Creating new substrings consumes O(N) extra memory, which is unnecessary.

Solutions

class Solution {private  static final Set<Character> VOWELS =      Set.of('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');public  boolean halvesAreAlike(String s) {    int cnt = 0, n = s.length() >> 1;    for (int i = 0; i < n; ++i) {      cnt += VOWELS.contains(s.charAt(i)) ? 1 : 0;      cnt -= VOWELS.contains(s.charAt(i + n)) ? 1 : 0;    }    return cnt == 0;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem