Jobs

Interviews

Discussions

Count the Number of Consistent Strings

Easy

Robinhood

2 views

Topics:

ArraysStrings

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.

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 <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Try coding it in LeetCode

Count the Number of Consistent Strings

Easy

Robinhood

2 views

Topics:

ArraysStrings

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.

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 <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `allowed` string or the strings in the `words` array be empty?
What are the possible character sets for the strings? Is it limited to lowercase English letters, or could it include uppercase letters, numbers, or other special characters?
What is the maximum length of the `allowed` string, and what is the maximum length of any string in the `words` array?
Are the characters in the `allowed` string guaranteed to be distinct as stated, or should I handle potential duplicates within `allowed`?
If a string in `words` is empty, should it be considered consistent if `allowed` is also empty, or should empty strings never be counted as consistent?

Brute Force Solution

Approach

The brute force method for this problem involves checking each word individually against the allowed characters. We want to find how many words only use characters from a given set of approved letters. We will do this by exhaustively checking each word.

Here's how the algorithm would work step-by-step:

Take the set of allowed letters and the first word.
For each letter in the word, check if that letter is in the set of allowed letters.
If any letter in the word is NOT in the allowed set, then the word is not consistent.
If every letter in the word IS in the allowed set, then the word IS consistent. Add one to our consistent word counter.
Repeat steps 2-4 for every other word in the list of words.
The final count of consistent words is our answer.

Code Implementation

def count_consistent_strings_brute_force(allowed_characters, words):
    consistent_string_count = 0

    for word in words:
        is_consistent = True

        # Check each letter in the word

        for letter in word:

            # If the letter isn't allowed, word is inconsistent
            if letter not in allowed_characters:

                is_consistent = False
                break

        # Increment the counter if it's a consistent string
        if is_consistent:

            consistent_string_count += 1

    return consistent_string_count

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each of the 'm' words in the input array. For each word, it iterates through the characters of the word, where the average length of the words is 'n'. Inside the inner loop, it checks if the current character exists in the 'allowed' string. Therefore, the time complexity is proportional to the product of the number of words and the average length of each word, resulting in O(m*n).

Space Complexity

O(1) – The provided algorithm iterates through the input words and their characters, but it does not create any auxiliary data structures that scale with the input size to store intermediate results. It uses a counter for consistent words, and temporary variables for iteration, but the space required for these remains constant irrespective of the number of words or the length of the allowed string. Therefore, the space complexity is constant, or O(1).

Optimal Solution

Approach

We need to figure out how many words are made up entirely of specific allowed letters. The fastest way is to create a way to quickly check if a word is acceptable, then go through the words and count how many pass the check.

Here's how the algorithm would work step-by-step:

First, we'll build a quick reference to see if each letter is allowed. Think of it like making a checklist of allowed letters.
Then, we will go through each word one by one.
For each word, we'll check if every single letter in that word is on our allowed checklist.
If every letter in the word is on the checklist, we mark that word as consistent.
Finally, we simply count up all the words that we marked as consistent, and that's our answer.

Code Implementation

def count_consistent_strings(allowed_characters, words):
    allowed_set = set(allowed_characters)
    consistent_word_count = 0

    # Iterate through each word to check its consistency
    for word in words:
        is_consistent = True

        # Iterate through each character of the current word
        for character in word:

            #Check if the character exists in the allowed set
            if character not in allowed_set:
                is_consistent = False
                break

        # If the word is consistent, increment counter
        if is_consistent:
            consistent_word_count += 1

    # Return the number of consistent strings
    return consistent_word_count

Big(O) Analysis

Time Complexity

O(m + n*k) – Let m be the length of the allowed string, n be the number of words in the words array, and k be the maximum length of a word in the words array. Creating the allowed character set takes O(m) time. Then, for each of the n words, we iterate through its characters (up to k characters). Therefore, checking the consistency of all words takes O(n*k) time. The overall time complexity is O(m + n*k).

Space Complexity

O(1) – The solution builds a quick reference to check if each letter is allowed. This can be implemented using a fixed-size set or boolean array representing the alphabet (e.g., 26 characters for English). The number of allowed letters does not depend on the number of input words. Therefore, the space used for this reference is constant. The solution also uses a counter for the number of consistent strings, which takes constant space. Thus, the auxiliary space used is constant, irrespective of the input size.

Edge Cases

Case	How to Handle
allowed is null or empty	Return 0 because no string in words can be consistent without allowed characters.
words is null or empty	Return 0 because there are no words to check for consistency.
words contains an empty string	An empty string is considered consistent if allowed is not empty and inconsistent if allowed is empty (already handled above).
allowed contains an empty string (which is invalid based on the problem description that allowed consists of distinct characters)	If allowed is empty this case should already be handled and the string is inconsistent since no character could be allowed.
words array contains very long strings	The solution should iterate through each character in the word only once to check if all characters are in allowed, leading to O(n*m) complexity (n is word length and m is words array length).
allowed string contains all possible characters (e.g., all lowercase letters)	The solution should correctly identify all words as consistent without error.
words array contains a string with unicode characters not in allowed	The solution should support unicode characters and correctly identify such a word as inconsistent (using a set would handle this well).
Large input size for the words array (e.g. 10^4 elements)	The chosen data structure (like set for allowed) and algorithm (iterating words) should handle this scale with reasonable time complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `allowed` string or the strings in the `words` array be empty?
What are the possible character sets for the strings? Is it limited to lowercase English letters, or could it include uppercase letters, numbers, or other special characters?
What is the maximum length of the `allowed` string, and what is the maximum length of any string in the `words` array?
Are the characters in the `allowed` string guaranteed to be distinct as stated, or should I handle potential duplicates within `allowed`?
If a string in `words` is empty, should it be considered consistent if `allowed` is also empty, or should empty strings never be counted as consistent?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the set of allowed letters and the first word.
For each letter in the word, check if that letter is in the set of allowed letters.
If any letter in the word is NOT in the allowed set, then the word is not consistent.
If every letter in the word IS in the allowed set, then the word IS consistent. Add one to our consistent word counter.
Repeat steps 2-4 for every other word in the list of words.
The final count of consistent words is our answer.

Code Implementation

def count_consistent_strings_brute_force(allowed_characters, words):
    consistent_string_count = 0

    for word in words:
        is_consistent = True

        # Check each letter in the word

        for letter in word:

            # If the letter isn't allowed, word is inconsistent
            if letter not in allowed_characters:

                is_consistent = False
                break

        # Increment the counter if it's a consistent string
        if is_consistent:

            consistent_string_count += 1

    return consistent_string_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we'll build a quick reference to see if each letter is allowed. Think of it like making a checklist of allowed letters.
Then, we will go through each word one by one.
For each word, we'll check if every single letter in that word is on our allowed checklist.
If every letter in the word is on the checklist, we mark that word as consistent.
Finally, we simply count up all the words that we marked as consistent, and that's our answer.

Code Implementation

def count_consistent_strings(allowed_characters, words):
    allowed_set = set(allowed_characters)
    consistent_word_count = 0

    # Iterate through each word to check its consistency
    for word in words:
        is_consistent = True

        # Iterate through each character of the current word
        for character in word:

            #Check if the character exists in the allowed set
            if character not in allowed_set:
                is_consistent = False
                break

        # If the word is consistent, increment counter
        if is_consistent:
            consistent_word_count += 1

    # Return the number of consistent strings
    return consistent_word_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
allowed is null or empty	Return 0 because no string in words can be consistent without allowed characters.
words is null or empty	Return 0 because there are no words to check for consistency.
words contains an empty string	An empty string is considered consistent if allowed is not empty and inconsistent if allowed is empty (already handled above).
allowed contains an empty string (which is invalid based on the problem description that allowed consists of distinct characters)	If allowed is empty this case should already be handled and the string is inconsistent since no character could be allowed.
words array contains very long strings	The solution should iterate through each character in the word only once to check if all characters are in allowed, leading to O(n*m) complexity (n is word length and m is words array length).
allowed string contains all possible characters (e.g., all lowercase letters)	The solution should correctly identify all words as consistent without error.
words array contains a string with unicode characters not in allowed	The solution should support unicode characters and correctly identify such a word as inconsistent (using a set would handle this well).
Large input size for the words array (e.g. 10^4 elements)	The chosen data structure (like set for allowed) and algorithm (iterating words) should handle this scale with reasonable time complexity.