Problem of The Day: Count the Number of Consistent Strings

Problem Statement

Intuition

The problem is asking to count how many strings in the words list consist only of characters present in the allowed string. The first thought is to use a set to check if each word contains only valid characters, since set lookup is efficient and the problem doesn’t require ordering or duplicates.

Approach

1. Convert the allowed string into a set allowed_set, which allows for O(1) lookups.
2. Initialize a counter res to count how many words meet the criteria.
3. Iterate over each word in the words list:
   • Convert the word to a set to remove duplicate characters.
   • For each character in the word, check if it exists in allowed_set.
   • If a word contains any character not in the allowed_set, break the loop.
   • If all characters in the word are valid, increment the res counter.
4. Return the count res after checking all words.

Complexity

• Time complexity:

  The time complexity is \(O(n \cdot m)\), where \(n\) is the number of words in the words list and \(m\) is the average length of each word. This is because for each word, we need to check each of its characters against the allowed_set.

• Space complexity: The space complexity is \(O(1)\) for the counter and temporary variables, but \(O(k)\) for the allowed_set and \(O(m)\) for each word set, where \(k\) is the number of unique characters in allowed and \(m\) is the size of the word.

Code

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        res = 0
        allowed_set = set(allowed)
        for word in words:
            word_set = set(word)
            for c in word_set:
                if c not in allowed_set:
                    break
            else:
                res += 1
        return res

Editorial

Approach 1: Brute Force

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        consistent_count = 0

        # Iterate through each word in the words list
        for word in words:
            is_word_consistent = True

            # Check each character in the current word
            for char in word:
                is_char_allowed = False

                # Check if the current character is in the allowed string
                for allowed_char in allowed:
                    if allowed_char == char:
                        is_char_allowed = True
                        break  # Character found, no need to continue searching

                # If the character is not allowed, mark the word as inconsistent
                if not is_char_allowed:
                    is_word_consistent = False
                    break  # No need to check remaining characters

            # If the word is consistent, increment the count
            if is_word_consistent:
                consistent_count += 1

        return consistent_count

• time: O(m * n * k)
• space: O(1)

Approach 2: Boolean Array

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # Create a boolean list to mark which characters are allowed
        is_allowed = [False] * 26

        # Mark all characters in 'allowed' as True in the is_allowed list
        for char in allowed:
            is_allowed[ord(char) - ord("a")] = True

        consistent_count = 0

        # Iterate through each word in the words list
        for word in words:
            is_consistent = True

            # Check each character of the current word
            for char in word:
                # If any character is not allowed, mark as inconsistent and break
                if not is_allowed[ord(char) - ord("a")]:
                    is_consistent = False
                    break

            # If the word is consistent, increment the count
            if is_consistent:
                consistent_count += 1

        return consistent_count

• time: O(m + n * k)
• space: O(1)

Approach 3: Hash Set

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # Create a set to store the allowed characters
        allowed_chars = set(allowed)

        consistent_count = 0

        # Iterate through each word in the 'words' list
        for word in words:
            # Check if all characters in the word are in allowed_chars
            if all(char in allowed_chars for char in word):
                consistent_count += 1

        # Return the total count of consistent strings
        return consistent_count

• time: O(m + n * k)
• space: O(m)

Approach 4: Bit Manipulation

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        # Create a bitmask representing the allowed characters
        allowed_bits = 0

        # Set the corresponding bit for each character in allowed
        for char in allowed:
            allowed_bits |= 1 << (ord(char) - ord("a"))

        consistent_count = 0

        # Iterate through each word in the words list
        for word in words:
            is_consistent = True

            # Check each character in the word
            for char in word:
                # Calculate the bit position for the current character
                bit = (allowed_bits >> (ord(char) - ord("a"))) & 1

                # If the bit is 0, the character is not allowed
                if not bit:
                    is_consistent = False
                    break

            # If the word is consistent, increment the count
            if is_consistent:
                consistent_count += 1

        return consistent_count

• time: O(m + n * k)
• space: O(1)