Problem Breakdown
We are given two lists of strings, A and B. We need to find words in A that satisfy a specific condition relative to all words in B. A word is considered a subset of word if every character present in appears in , including multiplicity (frequency).
Goal: Return the list of universal words from A, where “universal” means for every word , is a subset of that specific word from A.
Constraints & Inputs:
- Lengths: .
- Word lengths: .
- Characters: Lowercase English letters (‘a’-‘z’).
- Output order does not matter.
Intuition
The core challenge is checking if a word in A satisfies the requirements of all words in B. A naive approach would check every pair individually, leading to .
Key Insight:
For any character (e.g., ‘e’), if one word in B requires 3 occurrences and another requires 2, a universal candidate from A must have at least occurrences of ‘e’. We can aggregate the requirements for all characters across all words in B into a single “super-map” (or frequency array). This map stores the maximum count required for each character. Once this aggregated requirement is computed (), we only need to check if words in A meet these static requirements, reducing the verification step significantly.
Approach
-
Aggregate Requirements: Initialize a fixed-size array (size 26) representing counts for ‘a’ through ‘z’. Iterate through every word in list
B. For each character found in any word ofB, update our requirement map to store the maximum frequency seen so far for that specific character.- Example: If “ee” is in B, we need 2 ‘e’s. If later “eee” appears (hypothetically), we update max needed ‘e’ count to 3.
-
Validate Candidates: Iterate through each word in list
A. Count the frequency of characters for this specific candidate using a similar fixed-size array or dictionary.- Compare the character counts of the current word against our aggregated requirement map from Step 1.
- If for any character, the count in is less than the required maximum (from
B), then cannot be universal.
-
Result Collection: Append valid words to a result list and return it at the end.
Complexity Analysis
- Time Complexity: , where is the maximum word length (bounded by 10).
- Processing
Btakes proportional time to total characters in all strings ofB. - Checking each string in
Ainvolves counting its chars () plus checking against a fixed-size requirement map (, which is constant ). Since 26 is small and bounded, the check per word is effectively linear with respect to input size.
- Processing
- Space Complexity: where . We use two arrays of size 26 (one for requirements, one for counting
A’s chars) regardless of input length. This counts as constant space relative to the number of words provided in constraints.
Solution
from typing import List
def wordSubsets(A: List[str], B: List[str]) -> List[str]:
# Step 1: Aggregate requirements from list B into a fixed-size array (size 26)
req_counts = [0] * 26
for b in B:
count_b = [0] * 26
# Count frequencies of characters in current word 'b'
for char in b:
idx = ord(char) - ord('a')
count_b[idx] += 1
# Update global requirements with max frequency needed so far
for i in range(26):
if req_counts[i] < count_b[i]:
req_counts[i] = count_b[i]
result = []
# Step 2: Check each word in A against the aggregated requirements from B
for a_word in A:
counts_a = [0] * 26
# Count frequencies of characters in current candidate 'a'
for char in a_word:
idx = ord(char) - ord('a')
counts_a[idx] += 1
valid = True
# Check if A's word meets all requirements from B
for i, req_count in enumerate(req_counts):
if counts_a[i] < req_count:
valid = False
break
if valid:
result.append(a_word)
return result
Edge Cases Handled
- Characters not present: If a character is required by
B(count > 0) but does not appear in any word ofA, the checkcounts_a[i] < req_countwill correctly identify it as invalid. - Empty Lists: While constraints specify lengths , if lists were empty, loops would simply skip and return an appropriate result (empty list).
- Multiplicity: The logic explicitly counts frequencies (
count_b[idx] += 1) rather than just checking existence, ensuring multiplicity requirements are met. - Performance: Using fixed-size arrays instead of hash maps avoids overhead associated with dictionary hashing for every character check, optimizing