1684. Count the Number of Consistent Strings

EasyBit ManipulationArrayHash TableString

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 the words list.
- all(c in s for c in w): For each word, we create a generator expression that yields True for each character c that is in the set s. The all() function checks if all values provided by this generator are True, meaning every character in the word is in the allowed set.
- The entire all() expression will be True if the word is consistent and False otherwise.
- sum(...): We are then using sum() 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 Evaluator

Example 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 the all() function to check if every character of a word is in the set s:

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 set s. So all(c in s for c in 'ab') will yield True for both characters, and all() will return True.
For the word "ac": the characters are 'a' and 'c', both of which are in the set s. The all() function will also return True.
For the word "de": the character 'd' is not in the set s, so all(c in s for c in 'de') will yield False when checking 'd', and all() will return False.
For the word "abc": all the characters 'a', 'b', and 'c' are in the set s, and all() will return True.
For the word "xy": neither 'x' nor 'y' is in the set s, so all(c in s for c in 'xy') will yield False immediately when checking 'x', and all() 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know