Odd-Length Strings Containing a Vowel
Given an array of strings arr, count how many strings s have ODD length AND contain at least one vowel (a, e, i, o, u, case-insensitive).
Complete: ``` count(arr: List[str]) -> int ``` Example: count(['abc', 'xy', 'Hi', 'rhythm']) returns 1 -- only 'abc' (length 3, contains 'a') satisfies both conditions; 'Hi' (len 2), 'rhythm' (len 6) and 'xy' (len 2) have even length. The empty string has length 0 (even) so never counts.
Hints
- Two independent predicates per string: odd length, and contains a vowel. AND them.
- Use a set of both-case vowels (or lowercase each char) and
any(...)so the scan short-circuits on the first vowel.
Worked Solution
How to Think About It: Two independent per-string predicates joined by AND — the heuristic is a single streaming pass with short-circuit evaluation, no sorting or precomputation. Odd length is $O(1)$; the vowel test is a membership scan that any(...) aborts at the first vowel, so worst case (no vowels) it reads the whole string but typically stops early. The one subtle point is case-insensitivity done right: rather than lowercasing every string (which allocates a copy per string), put both cases into the vowel set once. Order matters for cost too — testing len(s) % 2 == 1 *first* skips the character scan entirely for even-length strings.
Quick Estimate: Trace the spec ['abc','xy','Hi','rhythm']. Filter by odd length first: 'abc' (3, odd ✓), 'xy' (2 ✗), 'Hi' (2 ✗), 'rhythm' (6 ✗) — only 'abc' survives. Vowel check on 'abc': 'a' is a vowel ✓. Count $= \boxed{1}$, matching the spec. Sanity on the empty string mentioned in the prompt: len('') = 0 is even, filtered out before any vowel scan — never counted.
Approach: One sum over a generator with both predicates.
Formal Solution: Precompute the vowel set V = set('aeiouAEIOU') so membership is $O(1)$ and case is handled without transforming the input. Then sum 1 over each string satisfying both conditions:
```python def count(arr): V = set('aeiouAEIOU') return sum(1 for s in arr if len(s) % 2 == 1 and any(c in V for c in s)) ```
The and short-circuits: len(s) % 2 == 1 gates the vowel scan, so even-length strings cost $O(1)$; any(c in V for c in s) stops at the first vowel. The empty string has even length $0$, so it is excluded, as required.
Complexity $\boxed{O(\sum_s |s|)\text{ time (worst case)},\ O(1)\text{ extra space}}$ — the vowel set is a fixed 10 elements.
Answer: One pass counting odd-length strings that contain a vowel; the example returns 1.
Intuition
A warm-up filter-and-count: the answer is just how many array elements pass two cheap boolean tests, so one linear sweep with a short-circuiting vowel check does it.