Count the Number of Consistent Strings

Easy
434.

Count the Number of Consistent Strings

Count the Number of Consistent Strings is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.

You are given a string allowed of distinct characters and an array of strings words. A string is consistent if every one of its characters appears in allowed.

Return the number of consistent strings in words.

Example 1

Input
allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output
2
Explanation
"aaab" and "baa" use only a and b.

Example 2

Input
allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output
7

Example 3

Input
allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output
4

Constraints

  • 1 <= words.length <= 20
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • All characters of allowed are distinct lowercase letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} allowed
 * @param {string[]} words
 * @return {number}
 */
var countConsistentStrings = function(allowed, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Consistent Strings — Problem & Solution

Count the Number of Consistent Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count the Number of Consistent Strings is an easy coding problem on arrays, strings and hash table, asked in Amazon and Adobe interviews.

Problem statement

You are given a string allowed of distinct characters and an array of strings words. A string is consistent if every one of its characters appears in allowed.

Return the number of consistent strings in words.

Example 1

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: "aaab" and "baa" use only a and b.

Example 2

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7

Example 3

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4

Constraints

  • 1 <= words.length <= 20
  • 1 <= allowed.length <= 26
  • 1 <= words[i].length <= 10
  • All characters of allowed are distinct lowercase letters.

Hints for Count the Number of Consistent Strings

  1. Hint 1

    Turn allowed into a 26-bit mask once.

  2. Hint 2

    Turn each word into its own mask and check that it introduces no bit outside the allowed mask.

  3. Hint 3

    wordMask & ~allowedMask == 0 is exactly that test.

How to solve Count the Number of Consistent Strings

Turn allowed into a 26-bit mask; a word is consistent iff its own mask has no bit outside it.

Approach

  1. Build allowedMask.
  2. For each word build wordMask and count it if wordMask & ~allowedMask == 0.

Why it works

The mask encodes set membership, and word & ~allowed isolates letters not in the allowed set.

Complexity

  • Time — O(total characters)
  • Space — O(1)

Pitfalls

  • A hash set works equally well; the mask just avoids allocation.

Reference solution

Python

def countConsistentStrings(allowed: str, words) -> int:
    mask = 0
    for ch in allowed:
        mask |= 1 << (ord(ch) - 97)
    count = 0
    for w in words:
        word_mask = 0
        for ch in w:
            word_mask |= 1 << (ord(ch) - 97)
        if word_mask & ~mask == 0:
            count += 1
    return count

Java

public static int countConsistentStrings(String allowed, String[] words) {
    int mask = 0;
    for (int i = 0; i < allowed.length(); i++) mask |= 1 << (allowed.charAt(i) - 'a');
    int count = 0;
    for (String w : words) {
        int wordMask = 0;
        for (int i = 0; i < w.length(); i++) wordMask |= 1 << (w.charAt(i) - 'a');
        if ((wordMask & ~mask) == 0) count++;
    }
    return count;
}

C++

int countConsistentStrings(string allowed, vector<string>& words) {
    int mask = 0;
    for (char c : allowed) mask |= 1 << (c - 'a');
    int count = 0;
    for (const string& w : words) {
        int wordMask = 0;
        for (char c : w) wordMask |= 1 << (c - 'a');
        if ((wordMask & ~mask) == 0) count++;
    }
    return count;
}

JavaScript

var countConsistentStrings = function(allowed, words) {
    let mask = 0;
    for (let i = 0; i < allowed.length; i++) mask |= 1 << (allowed.charCodeAt(i) - 97);
    let count = 0;
    for (let i = 0; i < words.length; i++) {
        let wordMask = 0;
        for (let j = 0; j < words[i].length; j++) wordMask |= 1 << (words[i].charCodeAt(j) - 97);
        if ((wordMask & ~mask) === 0) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings