Skip to main content
Talentd

Count the Number of Consistent Strings - Solution & Explanation

EasyArrayHash TableStringBit Manipulation19 min readAsked at: Robinhood, Google, Bloomberg
Practice this problem

Problem Statement

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 <= 104
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • The characters in allowed are distinct.
  • words[i] and allowed contain 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.

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.

Code

PythonC++Java

Python

C++

Java

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as the space usage is dominated by the set of allowed characters, which is fixed at most 26.

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.
Space Complexity: O(1), because we use a constant amount of extra space regardless of input size.

Hash Table or Array—
Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Set for Allowed CharactersO(n * m)O(1)General case. Clean and readable solution with constant-time character checks.
BitmaskingO(n * m)O(1)When optimizing memory or demonstrating bit manipulation skills.

Video Solution

Count the Number of Consistent Strings - Leetcode 1684 - Python • NeetCodeIO • 8,132 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Consistent Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Pairs Of Similar Strings