algoadvance

Leetcode 2586. Count the Number of Vowel Strings in Range

Problem Statement

We need to determine how many strings in a given list are composed solely of vowels. We are given an index range [start, end] for the list, and we need to count only the strings within this specific range.

Clarifying Questions

1. Input Type and Range:
   • What type of input do we get for the strings list? An array or a list of strings?
   • Can the start and end indices be the same?
   • Are the indices start and end inclusive?
2. Case Sensitivity:
   • Are the vowel checks case-sensitive? For example, should ‘A’ and ‘a’ both be considered vowels?
   • Should we consider all possible vowels (a, e, i, o, u) for counting purposes?
3. Edge Cases:
   • How should empty strings be handled? Are they considered as strings made up solely of vowels?
   • What if the provided start and end indices are out of bounds?

Let’s assume from typical cases:

• The input will be a list of strings.
• Indices are inclusive.
• Vowels to consider are a, e, i, o, u in both uppercase and lowercase.
• Empty strings are not counted as vowels strings.

Strategy

1. Extract Sublist: Fetch the sublist from the given range [start, end].
2. Check Vowels: Check if each string in the sublist is composed solely of vowels.
3. Count: Maintain a count of the strings that meet the above condition.

Code

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

public class VowelStringCounter {

    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 int countVowelStringsInRange(List<String> strings, int start, int end) {
        // Validate indices
        if (start < 0) start = 0;
        if (end >= strings.size()) end = strings.size() - 1;
        if (start > end) return 0;

        int count = 0;
        
        for (int i = start; i <= end; i++) {
            if (isVowelString(strings.get(i))) {
                count++;
            }
        }
        
        return count;
    }
    
    private boolean isVowelString(String str) {
        if (str == null || str.isEmpty()) return false;
        for (char c : str.toCharArray()) {
            if (!VOWELS.contains(c)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        VowelStringCounter counter = new VowelStringCounter();
        List<String> strings = List.of("aeiou", "ACE", "OU", "a", "bcd");
        System.out.println(counter.countVowelStringsInRange(strings, 0, 2));  // Output: 2
        System.out.println(counter.countVowelStringsInRange(strings, 1, 4));  // Output: 1
    }
}

Time Complexity

• Extract Sublist: This is effectively O(1) because we iterate over a specific sub-range directly.
• Check Vowels: For each string in the sublist (let’s assume the length of the sublist is n), we check each character within the string. Assuming the average length of each string is m, checking each character results in a time complexity of O(m).
• Overall Time Complexity:
  • Iterating over the sublist: O(n)
  • Each string check: O(m)
  • Final complexity: O(n * m)

Space Complexity

• Space for Vowel Set: Constant space O(1).
• Overall Space Complexity: O(1) aside from the input storage.

This approach efficiently checks and counts the vowel strings within the specified range in optimal time.

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?