Dare2Solve
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
.
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.
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 the allowed
set. This can be done using a simple iteration or using helper functions like all()
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.
O(L)
, where L
is the length of the allowed
string.O(W)
, where W
is the length of the word. In the worst case, iterating through all words takes O(N * M)
, where N
is the number of words and M
is the average length of a word.O(N * M + L)
.O(L)
, where L
is the length of the allowed
string.O(L)
.class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
unordered_set<char> 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;
}
};
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
class Solution {
public int countConsistentStrings(String allowed, String[] words) {
Set<Character> 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;
}
}
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;
};