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

Complexity

  • ⏰ Time complexity: O(n + m.k). Creating the bitmask for the allowed string involves iterating through its characters, taking O(n) time. Then we process each word. Generating the bitmask for the word involves iterating through its characters, taking O(k) time given its length is k and the comparing the word with allowed bitmask takes O(1) time.
  • 🧺 Space complexity: O(1). Only a few integers are used for bitmasks and counters.