Count the Number of Consistent Strings - Practice Coding Problems

Count the Number of Consistent Strings - Problem

You are given a string allowed consisting of distinct characters and an array of strings words.

A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Input & Output

Example 1 — Basic Case

$ Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]

› Output: 2

💡 Note: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2 — All Valid

$ Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]

› Output: 7

💡 Note: All strings are consistent since they only use allowed characters a, b, c.

Example 3 — None Valid

$ Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]

› Output: 4

💡 Note: Strings "cc", "acd", "ac", and "d" are consistent. Others contain characters not in "cad".

Constraints

1 ≤ words.length ≤ 10⁴
1 ≤ allowed.length ≤ 26
1 ≤ words[i].length ≤ 10
The characters in allowed are distinct
words[i] and allowed contain only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

allowed="ab", words=["ad","bd","aaab","baa","badab"]

Check Each Word

Verify if all characters in each word exist in allowed

Count Valid

"aaab" and "baa" are consistent → count = 2

Key Takeaway

🎯 Key Insight: Pre-process allowed characters into a hash set or bitmask for fast O(1) character lookups

Asked in

a Amazon 15 M Microsoft 8

The optimal approach uses a hash set to store allowed characters for O(1) lookups. For each word, check if all characters exist in the set. The bit manipulation approach is even more efficient, using bitmasks for ultra-fast character verification. Time: O(k + n×m), Space: O(k) for hash set or O(1) for bit manipulation.

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation	O(k + n × m)	O(1)	Use bit masking to represent allowed characters for ultra-fast checking
Brute Force	O(n × m × k)	O(1)	Check each character of every word against the allowed string
Hash Set Optimization	O(k + n × m)	O(k)	Use hash set for O(1) character lookup instead of linear search

Bit Manipulation — Algorithm Steps

Create bitmask for allowed characters
For each word, create its character bitmask
Use bitwise AND to check if word's characters are subset of allowed

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Mask

Convert allowed characters to bitmask

Word Masks

Create bitmask for each word

Subset Check

Use bitwise AND to check if word ⊆ allowed

Code -

solution.c — C

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

int solution(char* allowed, char** words, int wordsSize) {
    // Create bitmask for allowed characters
    int allowedMask = 0;
    for (int i = 0; allowed[i] != '\0'; i++) {
        allowedMask |= 1 << (allowed[i] - 'a');
    }
    
    int count = 0;
    for (int i = 0; i < wordsSize; i++) {
        // Create bitmask for current word
        int wordMask = 0;
        for (int j = 0; words[i][j] != '\0'; j++) {
            wordMask |= 1 << (words[i][j] - 'a');
        }
        
        // Check if word's characters are subset of allowed
        if ((wordMask & allowedMask) == wordMask) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char allowed[1000];
    fgets(allowed, sizeof(allowed), stdin);
    allowed[strcspn(allowed, "\n")] = 0;
    
    char wordsLine[10000];
    fgets(wordsLine, sizeof(wordsLine), stdin);
    wordsLine[strcspn(wordsLine, "\n")] = 0;
    
    // Parse JSON array manually
    char** words = malloc(1000 * sizeof(char*));
    int wordsSize = 0;
    char* token = strtok(wordsLine + 1, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end >= token && (*end == ' ' || *end == '"' || *end == ']')) {
            *end = '\0';
            end--;
        }
        words[wordsSize] = malloc((strlen(token) + 1) * sizeof(char));
        strcpy(words[wordsSize], token);
        wordsSize++;
        token = strtok(NULL, ",");
    }
    
    int result = solution(allowed, words, wordsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k + n × m)

k to build allowed mask, then n words with average m characters for bit operations

✓ Linear Growth

Space Complexity

O(1)

Only storing integer bitmasks, constant space regardless of input size

✓ Linear Space

23.5K Views

Medium Frequency

~10 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

Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler