Count the Number of Consistent Strings solution and explanation
Google
9 more videos on this problem
Count the Number of Consistent Strings - Leetcode 1684 - PythonNeetCodeIO · 12:59 · 8K views
Count the Number of Consistent Strings | Using Bit Manipulation | Leetcode 1684 | codestorywithMIKcodestorywithMIK · 14:34 · 5K views
Count the Number of Consistent Strings, Leetcode#1684 | Leetcode solutionEasyLeetcode · 9:24 · 3K views
LeetCode 1684. [easy] Count the Number of Consistent StringsFrancesco Manicardi · 3:17 · 1K views
1684. Count the Number of Consistent Strings (Leetcode Easy)Programming Live with Larry · 2:00 · 835 views
1684 Count the Number of Consistent Strings | Leetcode - EasyThe Humble Coder · 6:11 · 689 views
Leetcode | 1684. Count the Number of Consistent Strings | Easy | Java SolutionDeveloper Docs · 5:00 · 660 views
COUNT THE NUMBER OF CONSISTENT STRINGS | LEETCODE 1684 | PYTHON SOLUTIONCracking FAANG · 4:55 · 279 views
LeetCode 1684 | Count the Number of Consistent Strings | HashSet | JavaSleepy Cracker · 3:18 · 182 views
LeetCode 1684: Count the Number of Consistent Strings | C++/Java Solution | Problem of Day(12 Sept)Code Plethora · 6:14 · 142 views
The problem
You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.
Return the number of consistent strings in the array words.
Example 1:
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"] Output: 2 Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.
Example 2:
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"] Output: 7 Explanation: All strings are consistent.
Example 3:
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"] Output: 4 Explanation: Strings "cc", "acd", "ac", and "d" are consistent.
Constraints:
1 <= words.length <= 1041 <= allowed.length <= 261 <= words[i].length <= 10- The characters in
allowedare distinct. words[i]andallowedcontain only lowercase English letters.
Approach overview
Problem Overview: You receive a string allowed and an array of strings words. A word is consistent if every character in the word appears in allowed. The task is to count how many words satisfy this condition.
Approach 1: Using Set for Allowed Characters (O(n * m) time, O(1) space)
Store all characters from allowed in a hash set for constant-time membership checks. Iterate through each word in words, and for every character verify that it exists in the set. If any character is missing, mark the word as inconsistent and skip it. Hash lookups are O(1), so each word takes time proportional to its length. This approach relies on a hash table and works well because the alphabet size is small and lookups are extremely fast.
Approach 2: Using Bitmasking (O(n * m) time, O(1) space)
Instead of a set, encode the allowed characters into a 26-bit integer mask. Each bit represents whether a letter from 'a' to 'z' is allowed. While scanning a word, compute the bit for each character and check if that bit exists in the mask using a bitwise AND operation. If a character's bit is not set, the word is inconsistent. This approach leverages bit manipulation to replace hash lookups with fast bit operations. It uses constant memory and performs well when you want minimal overhead.
Both strategies iterate through the string characters of every word and validate them against the allowed set. Since each character is processed once, the runtime scales linearly with the total number of characters across all words.
Recommended for interviews: The hash set solution is the most commonly expected answer because it is simple and readable. It demonstrates proper use of constant-time lookups. The bitmasking version is a strong follow-up optimization that shows deeper understanding of character encoding and low-level operations.
Approach 1: Approach 1: Using Set for Allowed Characters
We can leverage the power of sets to efficiently check if a word is consistent with the allowed characters. By converting the string `allowed` into a set, we can perform constant time look-up operations for each character in the words.
We will iterate through each word and check if every character of the word is present in the allowed set. If all characters are present, the word is consistent. Otherwise, it is not. We count the number of consistent words and return it.
def countConsistentStrings(allowed, words):
allowed_set = set(allowed)
count = 0
for word in words:
if all(char in allowed_set for char in word):
count += 1
return countimport java.util.Set;
import java.util.HashSet;
public class Main {
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;
}
}#include <unordered_set>
#include <vector>
#include <string>
int countConsistentStrings(std::string allowed, std::vector<std::string>& words) {
std::unordered_set<char> allowed_set(allowed.begin(), allowed.end());
int count = 0;
for (const std::string& word : words) {
bool consistent = true;
for (char ch : word) {
if (allowed_set.find(ch) == allowed_set.end()) {
consistent = false;
break;
}
}
if (consistent) {
count++;
}
}
return count;
}This solution first converts the `allowed` string to a set so that we can efficiently check membership of each character. Then it iterates over each word and uses a generator expression to check if all characters in the word are in the `allowed_set`. If a word is consistent, it increments the count of consistent words.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), as the space usage is dominated by the set of allowed characters, which is fixed at most 26.
Approach 2: Approach 2: Using Bitmasking
An alternative approach to solve this problem is using bitmasking. We can represent the set of allowed characters as a bitmask, where each bit corresponds to a specific character ('a' could be the least significant bit and 'z' the most significant). This allows us to quickly check if a word is consistent by creating a bitmask of the word and verifying it against the allowed bitmask.
def countConsistentStrings(allowed, words):
allowed_mask = 0
for char in allowed:
allowed_mask |= 1 << (ord(char) - ord('a'))
count = 0
for word in words:
word_mask = 0
for char in word:
word_mask |= 1 << (ord(char) - ord('a'))
if word_mask | allowed_mask == allowed_mask:
count += 1
return count#include <vector>
#include <string>
int countConsistentStrings(std::string allowed, std::vector<std::string>& words) {
int allowed_mask = 0;
for (char c : allowed) {
allowed_mask |= 1 << (c - 'a');
}
int count = 0;
for (const std::string& word : words) {
int word_mask = 0;
for (char c : word) {
word_mask |= 1 << (c - 'a');
}
if ((word_mask & allowed_mask) == word_mask) {
count++;
}
}
return count;
}In this Python implementation, we first create a bitmask for the allowed characters. Then, for each word, we convert it into a bitmask and check it against the allowed bitmask using bitwise operations. A word is consistent if its bitmask ANDed with the allowed mask produces the word mask itself.
Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1), because we use a constant amount of extra space regardless of input size.
Approach 3: Hash Table or Array
A straightforward approach is to use a hash table or array s to record the characters in allowed. Then iterate over the words array, for each string w, determine whether it is composed of characters in allowed. If so, increment the answer.
The time complexity is O(m), and the space complexity is O(C). Here, m is the total length of all strings, and C is the size of the character set allowed. In this problem, C leq 26.
function countConsistentStrings(allowed: string, words: string[]): number {
const set = new Set([...allowed]);
const n = words.length;
let ans = n;
for (const word of words) {
for (const c of word) {
if (!set.has(c)) {
ans--;
break;
}
}
}
return ans;
}int countConsistentStrings(char* allowed, char** words, int wordsSize) {
int n = strlen(allowed);
int make[26] = {0};
for (int i = 0; i < n; i++) {
make[allowed[i] - 'a'] = 1;
}
int ans = wordsSize;
for (int i = 0; i < wordsSize; i++) {
char* word = words[i];
for (int j = 0; j < strlen(word); j++) {
if (!make[word[j] - 'a']) {
ans--;
break;
}
}
}
return ans;
}func countConsistentStrings(allowed string, words []string) (ans int) {
s := [26]bool{}
for _, c := range allowed {
s[c-'a'] = true
}
check := func(w string) bool {
for _, c := range w {
if !s[c-'a'] {
return false
}
}
return true
}
for _, w := range words {
if check(w) {
ans++
}
}
return ans
}impl Solution {
pub fn count_consistent_strings(allowed: String, words: Vec<String>) -> i32 {
let n = words.len();
let mut make = [false; 26];
for c in allowed.as_bytes() {
make[(c - b'a') as usize] = true;
}
let mut ans = n as i32;
for word in words.iter() {
for c in word.as_bytes().iter() {
if !make[(c - b'a') as usize] {
ans -= 1;
break;
}
}
}
ans
}
}Approach 4: Bit Manipulation
We can also use a single integer to represent the occurrence of characters in each string. In this integer, each bit in the binary representation indicates whether a character appears.
We simply define a function f(w) that can convert a string w into an integer. Each bit in the binary representation of the integer indicates whether a character appears. For example, the string ab can be converted into the integer 3, which is represented in binary as 11. The string abd can be converted into the integer 11, which is represented in binary as 1011.
Back to the problem, to determine whether a string w is composed of characters in allowed, we can check whether the result of the bitwise OR operation between f(allowed) and f(w) is equal to f(allowed). If so, increment the answer.
The time complexity is O(m), where m is the total length of all strings. The space complexity is O(1).
function countConsistentStrings(allowed: string, words: string[]): number {
const helper = (s: string) => {
let res = 0;
for (const c of s) {
res |= 1 << (c.charCodeAt(0) - 'a'.charCodeAt(0));
}
return res;
};
const mask = helper(allowed);
let ans = 0;
for (const word of words) {
if ((mask | helper(word)) === mask) {
ans++;
}
}
return ans;
}int helper(char* s) {
int res = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) {
res |= 1 << (s[i] - 'a');
}
return res;
}
int countConsistentStrings(char* allowed, char** words, int wordsSize) {
int mask = helper(allowed);
int ans = 0;
for (int i = 0; i < wordsSize; i++) {
if ((mask | helper(words[i])) == mask) {
ans++;
}
}
return ans;
}func countConsistentStrings(allowed string, words []string) (ans int) {
f := func(w string) (mask int) {
for _, c := range w {
mask |= 1 << (c - 'a')
}
return
}
mask := f(allowed)
for _, w := range words {
if (mask | f(w)) == mask {
ans++
}
}
return
}impl Solution {
fn helper(s: &String) -> i32 {
let mut res = 0;
for c in s.as_bytes().iter() {
res |= 1 << ((c - b'a') as i32);
}
res
}
pub fn count_consistent_strings(allowed: String, words: Vec<String>) -> i32 {
let mask = Self::helper(&allowed);
let mut ans = 0;
for word in words.iter() {
if (mask | Self::helper(word)) == mask {
ans += 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Set for Allowed Characters | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Approach 2: Using Bitmasking | Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. |
| Hash Table or Array | – |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set for Allowed Characters | O(n * m) | O(1) | General case. Clean and readable solution with constant-time character checks. |
| Bitmasking | O(n * m) | O(1) | When optimizing memory or demonstrating bit manipulation skills. |
Frequently asked questions
Is Count the Number of Consistent Strings easy or hard?
Count the Number of Consistent Strings is classified as an Easy problem on LeetCode with a high acceptance rate around 88%. The challenge mainly tests basic string traversal and efficient membership checks using sets or bit manipulation.
Count the Number of Consistent Strings Python/Java solution
In Python, store allowed characters in a set and check each character of every word. In Java, use a HashSet<Character> or a boolean array of size 26. Both implementations run in O(n * m) time and require only constant additional space.
How to solve Count the Number of Consistent Strings in O(n)?
Treat n as the total number of characters across all words. Preprocess the allowed characters into a set or bitmask, then scan each word and check every character against it. Each character is processed exactly once, giving linear time relative to total input size.
What is the best approach for Count the Number of Consistent Strings?
The hash set approach is the most practical solution. Store characters from the allowed string in a set and verify each character of every word using O(1) membership checks. This results in O(n * m) time where n is the number of words and m is the average word length, with constant extra space.
Is Count the Number of Consistent Strings asked at Google/Amazon/Meta?
Problems involving string validation with hash sets or bitmasks frequently appear in interviews at companies like Amazon and Meta. While this exact problem may vary, the pattern of checking characters against an allowed set is common in coding interviews.
What data structure is used in Count the Number of Consistent Strings?
The most common data structure is a hash set that stores allowed characters for constant-time lookups. An alternative approach uses a 26-bit integer mask to represent the alphabet, enabling fast checks using bitwise operations.
What is the time complexity of Count the Number of Consistent Strings?
The time complexity is O(n * m). Each of the n words is scanned character by character, and each lookup in the allowed set or bitmask takes constant time. The algorithm scales with the total number of characters across all words.