Scan each word in the array and check if all its characters exist in the allowed string. Use a hash set or bitmap for O(1) lookups to efficiently identify inconsistent characters. This approach avoids unnecessary nested loops and quickly counts consistent strings while highlighting the Array scanning plus hash lookup pattern.
Problem Statement
You are given a string allowed consisting of distinct lowercase characters and an array of strings words. A string is consistent if every character in the string appears in allowed. Return the total number of consistent strings found in words.
For example, given allowed = "ab" and words = ["ad","bd","aaab","baa","badab"], only "aaab" and "baa" are consistent because they only use characters 'a' and 'b'. Count these consistent strings and return the total.
Examples
Example 1
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.
Example 2
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
All strings are consistent.
Example 3
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Strings "cc", "acd", "ac", and "d" are consistent.
Constraints
- 1 <= words.length <= 104
- 1 <= allowed.length <= 26
- 1 <= words[i].length <= 10
- The characters in allowed are distinct.
- words[i] and allowed contain only lowercase English letters.
Solution Approach
Hash Set Lookup
Store all characters of allowed in a hash set. For each word, check every character against the set. If a character is missing, mark the word as inconsistent and skip counting it.
Bit Manipulation Optimization
Convert allowed characters into a bitmask where each bit represents a character. For each word, compute its bitmask and check if it fits entirely within the allowed bitmask. This provides faster membership checks for larger datasets.
Counting Consistent Strings
Iterate through words, using either hash set or bitmask checks. Increment a counter only for words where all characters are allowed. Return the counter as the total number of consistent strings.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(m + n \cdot k) |
| Space | O(1) |
Time complexity is O(m + n * k), where m is the length of allowed, n is the number of words, and k is the average word length, because each character is checked once. Space complexity is O(1) because the hash set or bitmask uses a fixed size of at most 26 bits for lowercase letters.
What Interviewers Usually Probe
- Expect recognition of the array scanning plus hash lookup pattern.
- Look for discussion on avoiding nested loops by using set or bitmap membership checks.
- Check if candidate handles edge cases like empty words or full alphabet allowed strings.
Common Pitfalls or Variants
Common pitfalls
- Using nested loops without a hash set leads to O(n * k * m) complexity and TLE.
- Forgetting that allowed contains only distinct characters, so duplicates in allowed are irrelevant.
- Failing to handle words with characters outside 'a'-'z' could miscount consistent strings.
Follow-up variants
- Return the list of consistent strings instead of the count.
- Allow repeated characters in allowed and verify consistency without extra preprocessing.
- Count strings consistent with multiple allowed sets and compare results.
How GhostInterview Helps
- Automatically identifies words violating the allowed character constraint to highlight inconsistencies.
- Provides optimized hash set and bitmask approaches to avoid timeouts in large arrays.
- Breaks down step-by-step counting for consistent strings to match the problem's pattern and reduce failure modes.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern used in Count the Number of Consistent Strings?
The problem uses array scanning plus hash lookup, allowing efficient checks for character consistency in each word.
Can bit manipulation replace hash sets for allowed character checks?
Yes, converting allowed characters to a bitmask enables constant-time membership checks and is more memory-efficient for small alphabets.
How do you handle empty words or an empty allowed string?
Empty words are always consistent, while an empty allowed string results in zero consistent strings since no characters are allowed.
What causes time limit exceeded errors in this problem?
Using nested loops to check each character against allowed without a hash set or bitmap can increase runtime significantly.
Is it necessary to pre-process allowed characters?
Yes, storing allowed characters in a hash set or bitmask ensures each character check is O(1) and avoids repeated linear scans.
Need direct help with Count the Number of Consistent Strings instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count the Number of Consistent Strings from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the number of good subsets in an integer array, where each subset's product is the product of distinct primes.
Open problem page#1366 Rank Teams by VotesRank Teams by Votes requires counting position-based votes and resolving ties with array scanning and hash lookup techniques efficiently.
Open problem page#2131 Longest Palindrome by Concatenating Two Letter WordsFind the maximum-length palindrome by combining two-letter words using array scanning and hash table lookups efficiently.
Open problem page