Domain 2MediumMEDIUM

Word Subsets

Identify words in A that contain all characters from every word in B with sufficient multiplicity by aggregating max frequency requirements.

Domain: medium•Updated: 2026-09-03
#frequency counting#array manipulation#O(N*L)#constant space

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 bb is considered a subset of word aa if every character present in bb appears in aa, including multiplicity (frequency).

Goal: Return the list of universal words from A, where “universal” means for every word b∈Bb \in B, bb is a subset of that specific word from A.

Constraints & Inputs:

  • Lengths: 1≤∣A∣,∣B∣≤10,0001 \le |A|, |B| \le 10,000.
  • Word lengths: 1≤∣word∣≤101 \le |word| \le 10.
  • 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 (a,b)(a, b) individually, leading to O(∣A∣⋅∣B∣⋅L)O(|A| \cdot |B| \cdot L).

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 max⁡(3,2)=3\max(3, 2) = 3 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 (O(∣B∣⋅L)O(|B| \cdot L)), we only need to check if words in A meet these static requirements, reducing the verification step significantly.

Approach

  1. Aggregate Requirements: Initialize a fixed-size array (size 26) representing counts for ‘a’ through ‘z’. Iterate through every word bb in list B. For each character found in any word of B, 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.
  2. Validate Candidates: Iterate through each word aa 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 aa against our aggregated requirement map from Step 1.
    • If for any character, the count in aa is less than the required maximum (from B), then aa cannot be universal.
  3. Result Collection: Append valid words to a result list and return it at the end.

Complexity Analysis

  • Time Complexity: O(∣A∣⋅L+∣B∣⋅L)O(|A| \cdot L + |B| \cdot L), where LL is the maximum word length (bounded by 10).
    • Processing B takes proportional time to total characters in all strings of B.
    • Checking each string in A involves counting its chars (O(L)O(L)) plus checking against a fixed-size requirement map (O(26)O(26), which is constant KK). Since 26 is small and bounded, the check per word is effectively linear with respect to input size.
  • Space Complexity: O(K)O(K) where K=26K=26. 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 of A, the check counts_a[i] < req_count will correctly identify it as invalid.
  • Empty Lists: While constraints specify lengths ≥1\ge 1, 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