1684. Count the Number of Consistent Strings
Problem Description
The problem provides us with a string allowed
which is made up of distinct characters, meaning no character is repeated in the string allowed
. Additionally, we are given an array of strings called words
. Our task is to determine how many strings in the array words
are "consistent."
A string is defined as consistent if every character in the string appears in the allowed
string. In other words, if there's even one character in a word that is not present in allowed
, then that word is not considered consistent.
The goal is to return the number of consistent strings in the array words
.
Intuition
To solve this problem, the intuitive approach is to check each word in words
and ensure all of its characters are contained within the allowed
string. To optimize this process, we convert the allowed
string to a set. Sets in Python are collections that provide O(1) time complexity for checking if an element is present, which is faster than if allowed
were a list or a string, where the time complexity would be O(n).
Once we have the set of allowed characters, we iterate over each word in words
. For each word, we check whether every character is in our set of allowed characters. We use the all()
function which returns True if all elements of the iterable (the characters in the word) are True (or if the iterable is empty).
The expression (c in s for c in w)
is a generator that yields True or False for each character c
in the word w
depending on whether c
is in the set s
or not. The all()
function takes this generator as input and evaluates to True only if every character in the word is in the set of allowed characters.
Finally, we use the sum()
function to count how many words are consistent by adding up 1 for every True result from the all()
check.
The result is the number of consistent strings in the words
array, which is what we return.
Solution Approach
The solution provided uses Python's set and comprehension features to perform the task efficiently.
-
The first step is to convert the
allowed
string into a set:s = set(allowed)
Converting to a set is significant because set operations in Python are usually faster than list or string operations. Specifically, checking for membership using the
in
operator is very fast for sets, taking O(1) time on average. -
Next, we use a list comprehension to iterate over each word in
words
:sum(all(c in s for c in w) for w in words)
This comprehensive line does several things:
for w in words
: We start by going over each word in thewords
list.all(c in s for c in w)
: For each word, we create a generator expression that yields True for each characterc
that is in the sets
. Theall()
function checks if all values provided by this generator are True, meaning every character in the word is in theallowed
set.- The entire
all()
expression will be True if the word is consistent and False otherwise. sum(...)
: We are then usingsum()
to add up all the True values. Since True is equivalent to 1 in Python,sum()
effectively counts the number of consistent strings.
This algorithm is very concise and takes advantage of Python's high-level operations to solve the problem with both simplicity and efficiency. The use of all()
combined with a generator expression and sum()
allows us to perform the entire operation in a single, readable line of code.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose the string allowed
contains the characters "abc"
and we have an array words
containing the words ["ab", "ac", "de", "abc", "xy"]
.
Now, let's apply the solution step by step:
-
We convert the
allowed
string into a set to expedite membership checks:s = set('abc') # This creates the set {'a', 'b', 'c'}
-
Next, we iterate over each word in
words
and use theall()
function to check if every character of a word is in the sets
:result = sum(all(c in s for c in w) for w in words)
Let's break this down for each word:
-
For the word
"ab"
: the characters are'a'
and'b'
, both of which are in the sets
. Soall(c in s for c in 'ab')
will yield True for both characters, andall()
will return True. -
For the word
"ac"
: the characters are'a'
and'c'
, both of which are in the sets
. Theall()
function will also return True. -
For the word
"de"
: the character'd'
is not in the sets
, soall(c in s for c in 'de')
will yield False when checking'd'
, andall()
will return False. -
For the word
"abc"
: all the characters'a'
,'b'
, and'c'
are in the sets
, andall()
will return True. -
For the word
"xy"
: neither'x'
nor'y'
is in the sets
, soall(c in s for c in 'xy')
will yield False immediately when checking'x'
, andall()
will return False.
So, we get the following results for our words
array:
"ab"
: Consistent"ac"
: Consistent"de"
: Not consistent"abc"
: Consistent"xy"
: Not consistent
Finally, the sum()
function would add up all the True values (represented as 1 in Python):
result = sum([True, True, False, True, False]) # This equals 3
Therefore, the output would be 3
, as there are three consistent strings in the array words
.
Solution Implementation
1class Solution:
2 def countConsistentStrings(self, allowed: str, words: list[str]) -> int:
3 # Convert the allowed string into a set for O(1) lookup times
4 allowed_chars = set(allowed)
5
6 # Count the words in which all the characters are in the allowed set
7 # Summing up the boolean values where True is counted as 1, False as 0
8 consistent_words_count = sum(all(char in allowed_chars for char in word) for word in words)
9
10 return consistent_words_count # Return the total count of consistent words
11
1class Solution {
2 // Method to count number of consistent strings
3 public int countConsistentStrings(String allowed, String[] words) {
4 // Array to keep track of allowed characters
5 boolean[] isAllowed = new boolean[26];
6
7 // Populate the isAllowed array with characters from the 'allowed' string
8 for (char c : allowed.toCharArray()) {
9 isAllowed[c - 'a'] = true;
10 }
11
12 // Initialize count for consistent strings
13 int count = 0;
14
15 // Iterate through each word in the array 'words'
16 for (String word : words) {
17 // If the word is consistent, increment the count
18 if (isConsistent(word, isAllowed)) {
19 count++;
20 }
21 }
22
23 // Return the total count of consistent strings
24 return count;
25 }
26
27 // Helper method to check if a word is consistent
28 private boolean isConsistent(String word, boolean[] isAllowed) {
29 // Iterate through each character in the word
30 for (int i = 0; i < word.length(); i++) {
31 // If the character is not in the allowed list, return false
32 if (!isAllowed[word.charAt(i) - 'a']) {
33 return false;
34 }
35 }
36
37 // Return true if all characters of the word are allowed
38 return true;
39 }
40}
41
1#include <vector>
2#include <string>
3#include <bitset>
4
5class Solution {
6public:
7 int countConsistentStrings(std::string allowed, std::vector<std::string>& words) {
8 // Initialize a bitset to store whether each letter in the alphabet is allowed
9 std::bitset<26> allowedLetters;
10 for (char ch : allowed) {
11 allowedLetters.set(ch - 'a');
12 }
13
14 // Counter for the number of consistent strings
15 int consistentCount = 0;
16
17 // Lambda function to check if all characters in a word are allowed
18 auto isConsistent = [&](std::string& word) {
19 for (char ch : word) {
20 // If any character is not allowed, return false immediately
21 if (!allowedLetters.test(ch - 'a')) return false;
22 }
23 // All characters in the word are allowed
24 return true;
25 };
26
27 // Iterate through each word and increment the consistent count if the word is consistent
28 for (std::string& word : words) {
29 if (isConsistent(word)) {
30 ++consistentCount;
31 }
32 }
33
34 // Return the final count of consistent strings
35 return consistentCount;
36 }
37};
38
1// Counts the number of words from the 'words' array that contain only characters from the 'allowed' string.
2// @param allowed - A string consisting of distinct lowercase English letters, representing the allowed characters.
3// @param words - An array of strings, where each string consists only of lowercase English letters.
4// @return The count of words from the 'words' array that are "consistent" - contain only characters from 'allowed'.
5function countConsistentStrings(allowed: string, words: string[]): number {
6 // Converts a string to a bitmask where each bit set represents the presence of a character in the string.
7 // @param str - A string to convert to a bitmask.
8 // @return A bitmask representing the characters of the input string.
9 const convertToBitmask = (str: string): number => {
10 let bitmask = 0;
11 for (const char of str) {
12 bitmask |= 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0));
13 }
14 return bitmask;
15 };
16
17 // Create a bitmask for the allowed characters.
18 const allowedMask = convertToBitmask(allowed);
19 let consistentCount = 0; // Initialize the count of consistent strings.
20
21 // Loop through each word in the array.
22 for (const word of words) {
23 // If the bitmask of the word OR'd with the allowedMask equals the allowedMask,
24 // it means the word contains only characters from 'allowed'.
25 if ((allowedMask | convertToBitmask(word)) === allowedMask) {
26 consistentCount++; // Increment count as the word is consistent.
27 }
28 }
29
30 // Return the total count of consistent strings.
31 return consistentCount;
32}
33
Time and Space Complexity
Time Complexity
The time complexity of the function depends on two factors: the length of the words
list meaning the number of words it contains (let's denote this number as n
) and the average length of the words (let's denote it as k
). The function iterates over each word and then over each character in the word to check if it is in the set s
. Checking membership in a set is an O(1)
operation on average. Therefore, the time complexity for checking one word is O(k)
, and for all the words it's O(n * k)
.
Space Complexity
The space complexity is O(s)
where s
is the number of unique characters in the allowed
string because these are stored in a set. The other variable that could contribute to space complexity is w
in the generator expression, but since the space required for w
is reused as the iteration proceeds and since the strings in words are input to the function and not duplicated by it, this does not add to the space complexity of the solution itself. The space complexity for the output of the sum function is O(1)
since it's accumulating the result into a single integer. Therefore, the overall space complexity is O(s) + O(1)
which simplifies to O(s)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!