⚡Flashcard Drill➔
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.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

统计一致字符串的数目

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致字符串 。请你返回 words 数组中一致字符串的数目。约束:1 ≤ words.length ≤ 10^4;1 ≤ allowed.length ≤ 26;1 ≤ words[i].length ≤ 10;allowed 中的字符互不相同。

核心要点

  • 集合包含判断(标准解) :把 allowed 转成集合,对每个单词 w 判断 set(w) &lt;= allowed_set (即 w 的字符集是 allowed 的子集)。
  • 为什么可以用集合而非计数 :allowed 中字符 互不相同 ,且题目只要求「每个字符都在 allowed 中」(不限制使用次数),因此集合包含即可。
  • 位掩码优化 :用 26 位整数表示字符集, mask_w &amp; ~mask_allowed == 0 即为一致字符串。常数极小,是竞赛常用技巧。
  • 复杂度 :n 个单词、每词长 L,总 O(总字符数)。

常见陷阱

  • 忘记本题与 1160 的差异 :1160(拼写单词)限制字母 使用次数 ,必须比较计数;本题不限制次数,集合包含即可。把两者混用会导致 1160 出错。
  • 用 w in allowed 判断 :这判断的是「w 是否为 allowed 的子串」,与题意完全无关。
  • 误以为 allowed 有重复字符 :题目保证互不相同,因此无需去重;但显式转集合是更稳健的写法。

参考实现

class Solution:
    def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
        a = set(allowed)
        return sum(1 for w in words if set(w) <= a)

# 位掩码版本(常数更小):
# mask = 0
# for c in allowed: mask |= 1 << (ord(c) - 97)
# return sum(1 for w in words
#            if all(mask >> (ord(c) - 97) & 1 for c in w))