🎨Now live: Try our Free AI Image Generation Feature

Description
Given a string allowed
consisting of distinct characters and an array of strings words
, a word is considered consistent if all characters in the word appear in the string allowed
. Your task is to count how many words in the array words
are consistent.
For example, if allowed = "abc"
and words = ["a", "b", "c", "ab", "ac", "abc", "d"]
, then the consistent words are ["a", "b", "c", "ab", "ac", "abc"]
, so the function should return 6
.
Intuition
The key observation is that a word is consistent if all of its characters are present in the allowed
string. Therefore, we can iterate over each word and check whether all of its characters exist in the set of allowed characters. The count of words satisfying this condition gives the answer.
Approach
- Preprocess the allowed string: Convert the
allowed
string into a set of characters for fast lookup. This ensures that checking if a character is allowed happens in constant time. - Iterate over the words: For each word in the
words
list, check if all characters of the word are present in theallowed
set. This can be done using a simple iteration or using helper functions likeall()
in Python. - Count consistent words: If all characters of a word are allowed, increment the count.
- Return the count: After processing all words, return the total number of consistent words.
Complexity
Time Complexity:
- Building the set of allowed characters takes
O(L)
, whereL
is the length of theallowed
string. - For each word, checking if all characters are allowed takes
O(W)
, whereW
is the length of the word. In the worst case, iterating through all words takesO(N * M)
, whereN
is the number of words andM
is the average length of a word. - Overall, the time complexity is
O(N * M + L)
.
Space Complexity:
- Storing the set of allowed characters takes
O(L)
, whereL
is the length of theallowed
string. - In addition, space is required to store the words, but it is not counted as additional space because it is part of the input.
- Thus, the space complexity is
O(L)
.
Code
C++
class Solution {
public:
int countConsistentStrings(string allowed, vector& words) {
unordered_set allowedSet(allowed.begin(), allowed.end());
int count = 0;
for (const string& word : words) {
bool consistent = true;
for (char c : word) {
if (allowedSet.find(c) == allowedSet.end()) {
consistent = false;
break;
}
}
if (consistent) count++;
}
return count;
}
};
Python
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
allowed_set = set(allowed)
count = 0
for word in words:
if all(c in allowed_set for c in word):
count += 1
return count
Java
class Solution {
public int countConsistentStrings(String allowed, String[] words) {
Set allowedSet = new HashSet<>();
for (char c : allowed.toCharArray()) {
allowedSet.add(c);
}
int count = 0;
for (String word : words) {
boolean consistent = true;
for (char c : word.toCharArray()) {
if (!allowedSet.contains(c)) {
consistent = false;
break;
}
}
if (consistent) count++;
}
return count;
}
}
JavaScript
var countConsistentStrings = function (allowed, words) {
let count = 0;
for (let i = 0; i < words.length; i++) {
const arr = [...new Set([...Array.from(words[i])])]
if (!arr.some(el => !allowed.includes(el))) count++;
};
return count;
};