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
wordsthat are consistent withallowed.
Implicit Constraints or Edge Cases:
- If
allowedis empty, no words can be consistent. - If any word in
wordscontains a character not inallowed, it is not consistent. - All characters in
allowedandwordsare 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
- Convert the
allowedstring into a set of characters. - Initialize a counter to keep track of consistent strings.
- Iterate through each word in the
wordsarray:- 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.
- 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
allowedstring, 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: Ifallowedis 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.