Domain 1EasyCORE

Count the Number of Consistent Strings

The problem requires us to determine how many strings in an array are "consistent" with a given string of allowed characters. A string is considered consistent if all its characters appear in the `allowed` string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1684. Count the Number of Consistent Strings

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 81.9%


Problem Breakdown

The problem requires us to determine how many strings in an array are “consistent” with a given string of allowed characters. A string is considered consistent if all its characters appear in the allowed string.

Inputs:

  • allowed: A string consisting of distinct lowercase English letters.
  • words: An array of strings, where each string consists of lowercase English letters.

Outputs:

  • The number of strings in words that are consistent with allowed.

Implicit Constraints or Edge Cases:

  • If allowed is empty, no words can be consistent.
  • If any word in words contains a character not in allowed, it is not consistent.
  • All characters in allowed and words are lowercase English letters.

Intuition

A brute-force approach would involve checking each character of every word against the allowed string, which could be inefficient if words are long or numerous. Instead, we can use a set to store the allowed characters for O(1) average-time complexity lookups. This allows us to efficiently check if all characters in a word are allowed.

Approach

  1. Convert the allowed string into a set of characters.
  2. Initialize a counter to keep track of consistent strings.
  3. Iterate through each word in the words array:
    • For each word, convert it into a set of characters.
    • Check if the set of characters in the word is a subset of the allowed set.
    • If it is, increment the counter.
  4. Return the counter.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. This is because we iterate through each word and check each character against the allowed set.
  • Space Complexity: O(k), where k is the length of the allowed string, due to the storage of the allowed characters in a set.

Solution

def countConsistentStrings(allowed: str, words: List[str]) -> int:
    # Convert allowed string to a set for O(1) lookups
    allowed_set = set(allowed)
    
    # Initialize counter for consistent strings
    consistent_count = 0
    
    # Iterate through each word in the words array
    for word in words:
        # Convert word to a set of characters
        word_set = set(word)
        
        # Check if all characters in word are in allowed_set
        if word_set.issubset(allowed_set):
            consistent_count += 1
    
    return consistent_count

Edge Cases Handled

  • Empty allowed: If allowed is empty, no words can be consistent because there are no allowed characters.
  • Words with unique characters: The approach handles words with unique characters correctly by checking each character individually.
  • Long words: The use of sets ensures that even long words are checked efficiently.