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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

1
2
3

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Using Set

The task is to count how many strings in the array words are composed solely of characters found in the string allowed. Here are the steps:

  1. Allowed Set: Convert the allowed string to a set for O(1) lookup times.
  2. Consistency Check: For each word, check if all characters are in the allowed set.
  3. Count Consistent Strings: Increment the count for each consistent word.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    // Function to count consistent strings
    public int countConsistentStrings(String allowed, String[] words) {
        // Convert allowed characters to a set for O(1) lookups
        HashSet<Character> allowedSet = new HashSet<>();
        for (char ch : allowed.toCharArray()) {
            allowedSet.add(ch);
        }

        // Check if a word is consistent with the allowed set
        int count = words.length; // let all words be consistent
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                if (!allowedSet.contains(ch)) {
                    count--;
                    break;
                }
            }
        }

        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # Convert allowed characters to a set for O(1) lookups
        allowed_set = set(allowed)

        def is_consistent(word):
            # Check if each character in the word is in the allowed set
            for ch in word:
                if ch not in allowed_set:
                    return False
            return True

        # Count consistent words
        consistent_count = 0
        for word in words:
            if is_consistent(word):
                consistent_count += 1

        return consistent_count

Complexity

  • ⏰ Time complexity: O(n + m.k), where n is the length of the allowed string and m is number of words and k is the length of the word.
    1. Conversion to Set: Converting the allowed string to a set takes O(n), where n is the length of the allowed string.
    2. Checking Consistency: For each word in the words list, we check if all characters are in the allowed_set.
      • This involves iterating through each character in the word.
      • The worst-case time complexity to check each word is O(k) where k is the length of the word.
      • Since there are m words and each word has at most k characters, the total time complexity for checking consistency is O(m * k).
  • 🧺 Space complexity: O(n) for storing allowed in set

Method 2 - Using Bitmask

Here is the approach:

  1. Each Character as a Bit:
    • There are 26 lowercase English letters, so we can use an integer with a 26-bit representation.
    • Each bit in the integer will represent whether a particular character is allowed or part of a word.
  2. Allowed Bitmask:
    • Convert the allowed string into a bitmask where each bit is set if the corresponding character exists in the allowed string.
  3. Word Bitmask:
    • For each word in the words array, create a bitmask to represent characters in the word.
  4. Consistency Check:
    • A word is consistent if its bitmask is a subset of the allowed bitmask. This can be checked using bitwise operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    // Function to count consistent strings
    public int countConsistentStrings(String allowed, String[] words) {
        // Convert allowed characters to a set for O(1) lookups
        int allowedMask = 0;
        for (char ch : allowed.toCharArray()) {
            allowedMask |= 1 << (ch - 'a');
        }

        // Check if a word is consistent with the allowed set
        int count = words.length; // let all words be consistent
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                int charMask = 1 << (ch - 'a');
                if ((allowedMask & charMask) == 0) {
                    count--;
                    break;
                }
            }
        }

        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # Create the bitmask for allowed characters
        allowed_mask = 0
        for ch in allowed:
            allowed_mask |= 1 << (ord(ch) - ord("a"))

        def get_bitmask(word):
            bitmask = 0
            for ch in word:
                bitmask |= 1 << (ord(ch) - ord("a"))
            return bitmask

        # Count consistent words
        consistent_count = 0
        for word in words:
            if get_bitmask(word) & ~allowed_mask == 0:
                consistent_count += 1

        return consistent_count