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

Description Hints 2 Solution Video 12:59

1684. Count the Number of Consistent Strings

Easy88.1% acceptance3 companies

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 <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Asked at 3 companies

Robinhood

Google Bloomberg

Topics

Hints open one at a time

Hint 1

A string is incorrect if it contains a character that is not allowed

Hint 2

Constraints are small enough for brute force

12:59

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution