Count the Number of Consistent Strings

Problem Statement

You are provided with two inputs:

1. A string named allowed which comprises distinct lowercase English characters.
2. An array of strings called words.

In this context, a string from the array words is termed consistent if every character within that string can be found in the allowed string.

The task is to determine and return the number of consistent strings within the provided array words. This problem taps into string manipulation and character checking processes comprehensively.

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.

Approach and Intuition

The main goal of this problem is to evaluate each string in the words array and check if all of its characters are present in the allowed string to classify it as consistent. To achieve this efficiently, follow these steps:

1. Convert the allowed string into a set of characters. This conversion provides O(1) complexity for character lookup, making it much faster than checking each character's existence by iterating through the allowed string.

2. Initialize a counter to track the number of consistent strings.

3. Go over each word in the words array and check if every character is in the set we created from allowed. If a character is found that’s not in the allowed set, you can conclude this word is inconsistent and skip to the next word.

4. For each word that passes the character check, increment your consistency counter.

5. Finally, after all words are processed, return the count of consistent strings.

Here are some additional insights into the approach:

• Using a set for the allowed characters optimizes the character lookup process, which is crucial because character checking is the central operation of the solution.
• Looping through each word and then through each character might seem like a nested operation, but both operations are relatively short due to constraints (maximum of 10 characters per word and 26 allowed characters).
• The count sequence when a character isn’t allowed in a word stops further unnecessary checks on that word, enhancing efficiency.

By following these guided steps, the given problem can be tackled to determine and count all consistent strings against the allowed characters effectively.

Solutions

class Solution {
public:
    int countValidStrings(string allowedChars, vector<string>& wordList) {
        // allowedMask will store the bitmask of allowed characters
        int allowedMask = 0;
    
        // Initialize bitmask for allowed characters
        for (char ch : allowedChars) {
            allowedMask |= 1 << (ch - 'a');
        }
    
        int validCount = 0;
    
        // Check all words in the wordList
        for (const string& word : wordList) {
            bool isValid = true;
    
            // Check each character's validity in the word
            for (char c : word) {
                // Mask for the current character
                int currentCharMask = (allowedMask >> (c - 'a')) & 1;
    
                // If this character is not allowed
                if (currentCharMask == 0) {
                    isValid = false;
                    break;
                }
            }
    
            // Increment the count if word is valid
            if (isValid) {
                validCount++;
            }
        }
    
        return validCount;
    }
};