# Count the Number of Consistent Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-the-number-of-consistent-strings)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-consistent-strings
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table, String
**Companies:** [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## 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 <= 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.

# Approaches
## Brute-Force with String Search
This approach iterates through each word and, for each character in the word, performs a linear search within the `allowed` string to check for its existence. This is the most straightforward but least efficient method.
**Time:** O(N * M * K), where N is the number of words, M is the maximum length of a word, and K is the length of the `allowed` string. For each of the M characters in each of the N words, we perform a linear scan of the `allowed` string, which takes O(K) time. · **Space:** O(1), as we only use a few variables to keep track of the count and state. No extra space proportional to the input size is used.
**Pros:** Simple to understand and implement.; Requires no extra data structures, leading to O(1) space complexity.
**Cons:** Highly inefficient for larger inputs, especially with a long `allowed` string, due to the nested loops and the O(K) check for each character.
### Explanation
The brute-force method directly translates the problem statement into code. We initialize a counter for consistent strings. Then, we iterate through each `word` in the input array `words`. For each `word`, we assume it's consistent and then check every one of its characters. The check involves searching for the character in the `allowed` string. A simple way to do this is with the `String.indexOf()` method. If `indexOf()` returns -1, it means the character is not present in `allowed`, so the word is not consistent. We can then stop checking the current word and move to the next. If we finish checking all characters of a word and haven't found any unallowed ones, we increment our counter.

```java
class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        int consistentCount = 0;
        for (String word : words) {
            boolean isConsistent = true;
            for (char c : word.toCharArray()) {
                if (allowed.indexOf(c) == -1) {
                    isConsistent = false;
                    break;
                }
            }
            if (isConsistent) {
                consistentCount++;
            }
        }
        return consistentCount;
    }
}
```
### Algorithm
*   Initialize `count = 0`.
*   For each `word` in `words`:
    *   Set a flag `is_consistent = true`.
    *   For each character `c` in `word`:
        *   If `c` is not found in `allowed` (using a linear search like `String.indexOf()`):
            *   Set `is_consistent = false`.
            *   Break the inner loop.
    *   If `is_consistent` is `true`, increment `count`.
*   Return `count`.

## Optimized Lookup with a HashSet
To improve the lookup time for allowed characters, we can pre-process the `allowed` string and store its characters in a `HashSet`. This allows for checking if a character is allowed in average O(1) time, significantly speeding up the process compared to a linear search.
**Time:** O(K + N * M), where K is the length of `allowed`, N is the number of words, and M is the maximum length of a word. It takes O(K) to build the set and O(N * M) to iterate through all characters of all words with O(1) lookups. · **Space:** O(K), for storing the K characters of the `allowed` string in a `HashSet`. Since K is at most 26, this is effectively O(1) constant space.
**Pros:** Much more efficient than the brute-force approach due to O(1) lookups.; The logic remains clear and readable.
**Cons:** Uses extra space for the HashSet.; There can be a slight overhead associated with hashing compared to direct array access or bitwise operations.
### Explanation
The bottleneck in the brute-force approach is the repeated linear search in the `allowed` string. We can optimize this by using a data structure that provides fast lookups. A `HashSet` is ideal for this. First, we iterate through the `allowed` string once and populate a `HashSet` with its characters. This setup step takes time proportional to the length of `allowed`. After that, for each character in each word, we can check for its presence in the `HashSet` in average O(1) time. The rest of the logic remains the same: iterate through words, check each character, and if an unallowed character is found, move to the next word. If a word passes all checks, increment the count.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        Set<Character> allowedChars = new HashSet<>();
        for (char c : allowed.toCharArray()) {
            allowedChars.add(c);
        }

        int consistentCount = 0;
        for (String word : words) {
            boolean isConsistent = true;
            for (char c : word.toCharArray()) {
                if (!allowedChars.contains(c)) {
                    isConsistent = false;
                    break;
                }
            }
            if (isConsistent) {
                consistentCount++;
            }
        }
        return consistentCount;
    }
}
```
### Algorithm
*   Create a `HashSet` named `allowed_set`.
*   For each character `c` in `allowed`, add `c` to `allowed_set`.
*   Initialize `count = 0`.
*   For each `word` in `words`:
    *   Set a flag `is_consistent = true`.
    *   For each character `c` in `word`:
        *   If `allowed_set` does not contain `c` (an O(1) average time check):
            *   Set `is_consistent = false`.
            *   Break the inner loop.
    *   If `is_consistent` is `true`, increment `count`.
*   Return `count`.

## Most Efficient Approach: Bitmasking
This approach leverages bitwise operations for maximum efficiency. Since the input is restricted to 26 lowercase English letters, we can represent the set of allowed characters using a single 32-bit integer, known as a bitmask. Each bit from 0 to 25 corresponds to a letter 'a' through 'z'. This makes checking for an allowed character an extremely fast bitwise operation.
**Time:** O(K + N * M), where K is the length of `allowed`, N is the number of words, and M is the maximum length of a word. The time complexity is asymptotically the same as the HashSet approach, but bitwise operations are generally faster than hash lookups at the machine level. · **Space:** O(1), as we only use a single integer for the bitmask, regardless of the input size.
**Pros:** Extremely fast due to efficient bitwise operations.; Minimal space usage (a single integer), making it the most space-efficient solution.; The most optimal solution for the given constraints.
**Cons:** The logic might be slightly less intuitive for those unfamiliar with bitmasking.
### Explanation
Given that the character set is small and fixed (26 lowercase letters), we can use a bitmask as a highly efficient alternative to a HashSet or a boolean array. We use a single integer where each of the first 26 bits represents a letter of the alphabet. We first create this `allowedMask` by iterating through the `allowed` string. For each character, we set its corresponding bit to 1. Then, when we check the characters of each `word`, we can determine if a character is allowed by checking if its corresponding bit is set in the `allowedMask`. This check is done using a bitwise AND operation, which is extremely fast at the hardware level.

```java
class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        int allowedMask = 0;
        for (char c : allowed.toCharArray()) {
            allowedMask |= (1 << (c - 'a'));
        }

        int consistentCount = 0;
        for (String word : words) {
            boolean isConsistent = true;
            for (char c : word.toCharArray()) {
                // Check if the bit for the character is NOT set in the mask
                if ((allowedMask & (1 << (c - 'a'))) == 0) {
                    isConsistent = false;
                    break;
                }
            }
            if (isConsistent) {
                consistentCount++;
            }
        }
        return consistentCount;
    }
}
```
### Algorithm
*   Initialize an integer `mask = 0`.
*   For each character `c` in `allowed`:
    *   Set the bit corresponding to `c`: `mask = mask | (1 << (c - 'a'))`.
*   Initialize `count = 0`.
*   For each `word` in `words`:
    *   Set a flag `is_consistent = true`.
    *   For each character `c` in `word`:
        *   Check if the bit for `c` is set in `mask` using `(mask & (1 << (c - 'a')))`.
        *   If the result is 0, the character is not allowed.
            *   Set `is_consistent = false`.
            *   Break the inner loop.
    *   If `is_consistent` is `true`, increment `count`.
*   Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int countConsistentStrings(String allowed, String[] words) {
    boolean[] s = new boolean[26];
    for (char c : allowed.toCharArray()) {
      s[c - 'a'] = true;
    }
    int ans = 0;
    for (String w : words) {
      if (check(w, s)) {
        ++ans;
      }
    }
    return ans;
  }
private
  boolean check(String w, boolean[] s) {
    for (int i = 0; i < w.length(); ++i) {
      if (!s[w.charAt(i) - 'a']) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countConsistentStrings(string allowed, vector<string> &words) {
    bitset<26> s;
    for (auto &c : allowed)
      s[c - 'a'] = 1;
    int ans = 0;
    auto check = [&](string &w) {
      for (auto &c : w)
        if (!s[c - 'a'])
          return false;
      return true;
    };
    for (auto &w : words)
      ans += check(w);
    return ans;
  }
};

```

### Python

```python
class Solution : def countConsistentStrings ( self , allowed : str , words : List [ str ]) -> int : s = set ( allowed ) return sum ( all ( c in s for c in w ) for w in words )
```