Find Words That Can Be Formed by Characters

Find Words That Can Be Formed by Characters - Problem

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once for each word in words).

Return the sum of lengths of all good strings in words.

Input & Output

Example 1 — Basic Case

$ Input: words = ["cat","bt","hat","tree"], chars = "atach"

› Output: 6

💡 Note: "cat" can be formed (c=1, a=1, t=1 all available), "bt" cannot (no 'b' in chars), "hat" can be formed (h=1, a=1, t=1 all available), "tree" cannot (need 2 'e' but chars has 0). Total length: 3 + 3 = 6

Example 2 — All Words Valid

$ Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"

› Output: 10

💡 Note: "hello" can be formed (all letters available), "world" can be formed, "leetcode" cannot be formed (missing some letters). Only "hello" (5) + "world" (5) = 10

Example 3 — No Valid Words

$ Input: words = ["dyiclysmffuhibgfvapygkorkuhn"], chars = "usdruypficfbpfbivlrhutcgvyjflhokvmcgllyderazxuxgjpxpppkxjfkdqcrxvlnxgtilxofuxnvdovgdlxihnbpanrdhpfhopgdkmahgkrr"

› Output: 0

💡 Note: The single word cannot be formed with the available characters, so return 0

Constraints

1 ≤ words.length ≤ 1000
1 ≤ words[i].length, chars.length ≤ 100
words[i] and chars consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and available characters

Process

Check each word against available character frequencies

Output

Sum of lengths of valid words

Key Takeaway

🎯 Key Insight: Count character frequencies once, then check each word's requirements against available characters

Asked in

G Google 25 a Amazon 18

The key insight is to count character frequencies once and compare requirements directly. Best approach uses frequency counting - count available characters in chars, then for each word count required characters and compare. Time: O(m + n×k), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Most Efficient Frequency Check	O(m + n × k)	O(1)	Count chars once, check each word without copying
Brute Force Character Counting	O(n × m × k)	O(1)	For each word, count characters in chars every time
Optimized Frequency Counting	O(m + n × k)	O(1)	Count chars frequency once, then check each word

Most Efficient Frequency Check — Algorithm Steps

Count frequency of each character in chars once
For each word, count required character frequencies
Compare word requirements against available characters
Add word length to sum if all requirements are met

Visualization

Tap to expand

Step-by-Step Walkthrough

Count available

Count all characters in chars string

Count needed

Count required characters for each word

Direct compare

Compare requirements vs available directly

Code -

solution.c — C

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

int solution(char words[][100], int wordCount, char* chars) {
    // Count frequency of characters in chars
    int charCount[26] = {0};
    for (int i = 0; chars[i]; i++) {
        charCount[chars[i] - 'a']++;
    }
    
    int totalLength = 0;
    
    for (int i = 0; i < wordCount; i++) {
        // Count required characters for this word
        int wordCount_arr[26] = {0};
        for (int j = 0; words[i][j]; j++) {
            wordCount_arr[words[i][j] - 'a']++;
        }
        
        int canForm = 1;
        // Check if all required characters are available
        for (int j = 0; j < 26; j++) {
            if (charCount[j] < wordCount_arr[j]) {
                canForm = 0;
                break;
            }
        }
        
        if (canForm) {
            totalLength += strlen(words[i]);
        }
    }
    
    return totalLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse words array (simplified)
    char words[100][100];
    int wordCount = 0;
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL && wordCount < 100) {
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, "[],\"\n ");
    }
    
    char chars[1000];
    fgets(chars, sizeof(chars), stdin);
    chars[strcspn(chars, "\n")] = 0;
    
    int result = solution(words, wordCount, chars);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n × k)

m chars length + n words × k average word length

✓ Linear Growth

Space Complexity

O(1)

Only two fixed-size frequency arrays for 26 lowercase letters

✓ Linear Space

52.0K Views

Medium Frequency

~15 min Avg. Time

1.5K 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

Most Efficient Frequency Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler