💬 Discord
Sign In
NeetCode #69LC-1684EasyArrays & Hashing
← Back to All Problems

#69 · #1684 · Count the Number of Consistent Strings(统计一致字符串的数目)

📌 Problem Statement & Constraints

You are given a string allowed of distinct characters and an array of strings words. A string is consistent if every character in it appears in allowed. Return the number of consistent strings. Constraints: 1 <= words.length <= 10^4, 1 <= allowed.length <= 26, all lowercase letters.

💡 Core Algorithmic Approaches

  1. Put the allowed characters in a hash set for O(1) membership tests.
  2. For each word, check that every character is in the set.
  3. Python's set.issuperset or the subset operator <= expresses this directly on character sets.
  4. The count of consistent strings is the answer.

💻 Benchmark Python3 Implementation

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        ok = set(allowed)
        return sum(1 for w in words if set(w) <= ok)   # subset test


# Early-exit variant, faster when most words fail
class Solution2:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        ok = set(allowed)
        res = 0
        for w in words:
            if all(ch in ok for ch in w):
                res += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters across all words): each character is tested once (plus the cost of building the word sets in the first variant).
💾 Space Complexity
O(1): the allowed set has at most 26 entries.

⚠️ Interview Pitfalls & Follow-ups

  • Using set(w) <= ok when the problem forbids duplicates: it does not matter here, since duplicates within a word do not change the character set.
  • Checking ok <= set(w): the direction is reversed -- you need the word's characters to be a subset of allowed.
  • Building a set for every word: correct, but the early-exit variant avoids the allocation and can stop at the first bad character.