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
- Put the allowed characters in a hash set for O(1) membership tests.
- For each word, check that every character is in the set.
- Python's
set.issupersetor the subset operator<=expresses this directly on character sets. - 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) <= okwhen 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 ofallowed. - 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.
🧩 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) <= allowed_set (即 w 的字符集是 allowed 的子集)。
- 为什么可以用集合而非计数 :allowed 中字符 互不相同 ,且题目只要求「每个字符都在 allowed 中」(不限制使用次数),因此集合包含即可。
- 位掩码优化 :用 26 位整数表示字符集, mask_w & ~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))