Word Subsets - Practice Coding Problems

Word Subsets - Problem

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity. For example, "wrr" is a subset of "warrior" but is not a subset of "world".

A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

Input & Output

Example 1 — Basic Universal Check

$ Input: words1 = ["warrior","world"], words2 = ["w","o","r"]

› Output: ["warrior","world"]

💡 Note: "warrior" contains w:2≥1, o:1≥1, r:3≥1. "world" contains w:1≥1, o:1≥1, r:1≥1. Both are universal.

Example 2 — Multiplicity Check

$ Input: words1 = ["warrior","world"], words2 = ["w","o","ld"]

› Output: ["world"]

💡 Note: For "ld", need l:1, d:1. "warrior" has l:0, d:0. "world" has l:1≥1, d:1≥1. Only "world" is universal.

Example 3 — No Universal Words

$ Input: words1 = ["abc","def"], words2 = ["xyz"]

› Output: []

💡 Note: Neither "abc" nor "def" contains x, y, or z. No words are universal.

Constraints

1 ≤ words1.length, words2.length ≤ 10⁴
1 ≤ words1[i].length, words2[i].length ≤ 10
words1[i] and words2[i] consist only of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

words1 candidates and words2 requirements

Subset Check

Verify each word1 contains all characters from all words2

Universal Words

Return words that satisfy all requirements

Key Takeaway

🎯 Key Insight: Merge all requirements first to avoid redundant character frequency checks

Asked in

G Google 25 f Facebook 18

The key insight is to merge all requirements from words2 into a unified character frequency map first, then check each word1 against this single requirement set. This eliminates redundant checking. Best approach uses optimized preprocessing. Time: O(n×k + m×k), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Word Against All	O(n × m × k)	O(k)	For each word in words1, check if it contains every word in words2
Optimized - Merge Requirements First	O(n × k + m × k)	O(k)	First merge all words2 into unified requirements, then check each word1 once

Brute Force - Check Each Word Against All — Algorithm Steps

Step 1: For each word in words1, create character frequency map
Step 2: For each word in words2, check if word1 has enough of each character
Step 3: If all words2 are subsets of current word1, add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Word

Take each word from words1

Check All

Verify against every word in words2

Add if Universal

If passes all checks, add to result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isSubset(char* word1, char* word2) {
    int count1[26] = {0};
    int count2[26] = {0};
    
    for (int i = 0; word1[i]; i++) {
        count1[word1[i] - 'a']++;
    }
    
    for (int i = 0; word2[i]; i++) {
        count2[word2[i] - 'a']++;
    }
    
    for (int i = 0; i < 26; i++) {
        if (count2[i] > count1[i]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    char* words1[1000];
    char* words2[1000];
    int n1 = 0, n2 = 0;
    
    // Read and parse words1
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            words1[n1] = malloc(strlen(token) + 1);
            strcpy(words1[n1], token);
            n1++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    // Read and parse words2
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            words2[n2] = malloc(strlen(token) + 1);
            strcpy(words2[n2], token);
            n2++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char* result[1000];
    int resultSize = 0;
    
    for (int i = 0; i < n1; i++) {
        bool isUniversal = true;
        for (int j = 0; j < n2; j++) {
            if (!isSubset(words1[i], words2[j])) {
                isUniversal = false;
                break;
            }
        }
        if (isUniversal) {
            result[resultSize++] = words1[i];
        }
    }
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        if (i > 0) printf(",");
        printf("\"%s\"", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

For each of n words in words1, check against m words in words2, each taking k characters to process

✓ Linear Growth

Space Complexity

O(k)

Character frequency maps store at most k characters per word

✓ Linear Space

31.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Word Against All — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler