037.md

1684. Count the Number of Consistent Strings

Difficulty: 🟢 Easy

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:

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.

Solutions

O(n) solution using set in Python3

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        count, char_set = 0, set(allowed)
        for word in words:
            if len(set(word).difference(char_set)) == 0:
                count += 1
        return count

The given solution counts the number of consistent strings by iterating through the words array and checking if each word is consistent.

The algorithm works as follows:

1. Initialize a count variable to 0 to keep track of the number of consistent strings.
2. Create a character set, char_set, from the allowed string using the set function.
3. Iterate through each word in the words array:
   • Check if the difference between the characters in the current word and the char_set is an empty set. If it is, it means all characters in the word are present in the allowed string, making it consistent. Increment the count by 1.
4. Return the count, which represents the number of consistent strings.

The algorithm checks each word in the words array to see if all its characters are present in the allowed string, and increments the count accordingly.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n * m), where n is the length of the words array and m is the maximum length of a word in the words array. The algorithm iterates through each word in the words array and performs a set difference operation, which takes O(m) time, for each word.

The space complexity of the algorithm is O(k), where k is the length of the allowed string. The algorithm creates a char_set set containing the characters from the allowed string, which takes O(k) space.

Summary

The given solution counts the number of consistent strings in the words array by checking if each word has all its characters present in the allowed string. It has a time complexity of O(n * m) and a space complexity of O(k), making it an efficient solution for the problem at hand.

O(n) solution using fixed length array in Python3

class Solution:
    def _get_counter(self, allowed: str) -> List[int]:
        counter = [0] * 26
        for char in allowed:
            counter[ord(char)-ord('a')] += 1
        return counter

    def _counter_difference(self, a: List[int], b: List[int]) -> List[int]:
        for i, count in enumerate(a):
            if count > 0:
                b[i] = 0
        return b

    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        count, allowed_counter = 0, self._get_counter(allowed)
        for word in words:
            word_counter = self._get_counter(word)
            if sum(self._counter_difference(allowed_counter, word_counter)) == 0:
                count += 1
        return count

The given solution uses a counter-based approach to determine the number of consistent strings in the words array.

The algorithm works as follows:

1. Define a private helper method, _get_counter(), which takes a string allowed as input and returns a list representing the count of each character in the string. The list has a length of 26, initialized with zeros.
   • Iterate through each character in the allowed string.
   • Increment the count for the corresponding character in the counter list by 1.
   • Return the counter list.
2. Define another private helper method, _counter_difference(), which takes two counter lists a and b as input and modifies b to represent the difference between a and b.
   • Iterate through each index and count in the a list.
   • If the count in a is greater than 0, set the count in b to 0.
   • Return the modified b list.
3. Define the main method, countConsistentStrings(), which takes the allowed string and the words array as input and returns the number of consistent strings in the words array.
   • Initialize a count variable to 0.
   • Obtain the counter list for the allowed string using the _get_counter() method.
   • Iterate through each word in the words array.
     • Obtain the counter list for the current word using the _get_counter() method.
     • Calculate the difference between the allowed counter and the current word counter using the _counter_difference() method.
     • If the sum of the modified counter list is 0, increment the count variable by 1.
   • Return the count variable.

The algorithm uses counter lists to track the counts of characters in the allowed string and words from the words array. It calculates the difference between the allowed counter and the word counter and determines if the word is consistent by checking if the sum of the modified counter is 0.

Analysis of Time and Space Complexity

The time complexity of this algorithm depends on the length of the words array and the length of each word. Let n be the length of the words array and m be the maximum length of a word. The algorithm iterates through each word in the words array and each character in the word, performing constant-time operations at each iteration. Therefore, the overall time complexity is O(n * m). Since m is fixed final result will be O(n).

The space complexity of the algorithm is O(1) since it uses a constant amount of extra space to store the counter lists and the count variable.

Summary

The given solution determines the number of consistent strings in the words array by using counter lists to track the counts of characters in the allowed string and words. It has a time complexity of O(n * m) and a space complexity of O(1), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.