Count the Number of Consistent Strings

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;
    }
};

This solution defines a function countValidStrings to determine the number of strings in a provided list (wordList) that consist only of characters found in a specified allowedChars string. The function efficiently handles this task through the utilization of bit manipulation strategies. Below summarizes the implementation steps in C++:

• Initialize an integer allowedMask to store a bitmask representing the characters allowed for valid strings. This bitmask is created by iterating over each character in allowedChars and setting the corresponding bit.

• Iterate through each word in wordList and determine its validity against allowedMask:

  • For each word, check each character to see if it exists in the allowedMask. This is achieved by shifting the allowedMask right by the alphabetical index of the character and checking the least significant bit.
  • If a character in the word is not present in the allowedMask, mark the word as invalid and break out of the checking loop.

• If a word passes the character check, increment the count of valid words.

• Finally, the function returns the total count of valid words.

The implementation leverages the efficiency of bitwise operations to check character inclusion, making the solution optimal for large input sizes.

class Solution {

    public int countAllowedStrings(String allowedChars, String[] wordList) {
        int allowedMask = 0;

        for (int i = 0; i < allowedChars.length(); i++) {
            allowedMask |= 1 << (allowedChars.charAt(i) - 'a');
        }

        int count = 0;

        for (String word : wordList) {
            boolean isAllowed = true;

            for (int i = 0; i < word.length(); i++) {
                int currentBit = (allowedMask >> (word.charAt(i) - 'a')) & 1;

                if (currentBit == 0) {
                    isAllowed = false;
                    break;
                }
            }

            if (isAllowed) {
                count++;
            }
        }

        return count;
    }
}

This Java program defines a method named countAllowedStrings aimed at determining how many strings within an array (wordList) consist solely of characters defined in the allowedChars string. The solution applies bit manipulation techniques to optimize the process of checking if each character in a word from the wordList is included in the allowedChars.

• Start by initializing an integer allowedMask to zero. This integer will use its bits to flag which characters are permitted.
• Iterate over each character in the allowedChars string:
  • Update allowedMask by setting the bit corresponding to each character. This is achieved by shifting the bit to the left according to the character's position in the alphabet.
• Initialize a counter count to keep track of how many strings from wordList are composed only of allowed characters.
• Iterate over each string in the wordList:
  • Assume initially that the string is allowed (isAllowed set to true).
  • For each character in the current word, determine its respective bit in allowedMask to check if the character is allowed:
    • If any character in the word has its corresponding bit not set in allowedMask, mark isAllowed as false and exit the inner loop.
  • If, after checking every character, the word is still marked as allowed, increase the count by one.

The method finally returns the count of consistent strings, which are those composed entirely of allowed characters. This approach reduces the time complexity compared to brute force methods, especially beneficial as the size of the input increases.

class Solution:
    def countValidWords(self, allowed_chars: str, word_list: List[str]) -> int:
        permitted_bits = 0
        for char in allowed_chars:
            permitted_bits |= 1 << (ord(char) - ord('a'))

        valid_count = 0
        for word in word_list:
            passes_check = True
            for char in word:
                character_bit = (permitted_bits >> (ord(char) - ord('a'))) & 1
                if character_bit == 0:
                    passes_check = False
                    break

            if passes_check:
                valid_count += 1

        return valid_count

In the given problem, the Python function countValidWords solves the task of counting how many strings in a list (word_list) consist only of characters in a specified set (allowed_chars). This is effectively an application of bit manipulation to efficiently check character permissions against a given set of allowed characters.

Here’s how the provided solution works:

1. Initially, the function defines an integer permitted_bits representing binary flags for each character. A 1 at any bit position in permitted_bits indicates that the corresponding character is allowed.

2. The function iterates through each character in allowed_chars, setting the corresponding bit in permitted_bits based on the ASCII value of the character minus the ASCII value of 'a' (i.e., for 'a' it sets bit position 0, for 'b' it sets bit position 1, and so forth).

3. After constructing the permitted_bits, the function initializes a counter valid_count to zero. This counter tallies the number of valid strings from the word_list that are completely composed of allowed characters.

4. For each word in word_list, it checks all characters in the word to ensure they are allowed by shifting the permitted_bits according to the character's position and checking the least significant bit. If it finds any character that is not allowed, it sets passes_check to False, and the loop breaks, moving to the next word.

5. If all characters in a word meet the allowed criteria (passes_check remains True), the function increments the valid_count.

6. The function ends by returning valid_count, which represents the number of words in word_list that consist solely of characters from allowed_chars.

This approach greatly optimizes the task by using bit manipulation, reducing the complexity and the need for multiple nested loop checks against the allowed_chars for every character in every word.