Editorial Series - LeetCode 1684. Count the Number of Consistent Strings

Problem Description

In this problem, you are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all the characters in the string appear in the string allowed.

Your task is to return the number of consistent strings in the array words.

Solution Description

There can be several solutions for this problem, however, I am going to utilize bit manipulation to solve it. So, let’s get started!

Suppose, you have two strings a and b. You want to determine whether string b has all the characters that are present in string a. So, what are you gonna do? Most likely, you will extract all the distinct common characters of strings a and b and then, verify whether all the distinct common characters comprise all the distinct characters in string a.

Now, let’s say you are given two integers consisting of 0s and 1s. And you are given the task to determine whether the integer b has1s in the same position as the integer a. How will you solve this problem? Here, you can utilize AND operation because if you do a bitwise AND of the two integers, 1s will remain in only those positions where both the integers have 1s. You can then check whether the integer a is equivalent to this newly generated integer.

a = 01010001
b = 01011101

(a AND b) = 01010001

a is equivalent to (a AND b)

---

a = 00011100
b = 11100011

(a AND b) = 00000000

a is not equivalent to (a AND b)

You can transform the string- problem to the integer- problem. How? Just take the integer 0 and then, for all the characters of a given string, set the desired bit positions in the integer 0. So, for example, if the string is abz, then the bit positions 0, 1 and 25 will be set. Since you are limited to just lowercase letters for this LeetCode problem, this technique is feasible for deriving the solution.

All you need to do now is to iterate over the words array and determine the count of consistent strings using the knowledge gathered so far.

Solution Code

If you are stuck with the solution of this problem, check the codes below:

C++

class Solution {
public:
    int markCharactersOf(string &word) {
        int result = 0;
        
        for (char ch : word) {
            int position = ch - 'a';
            result |= 1 << position;
        }
        
        return result;
    }
        
    int countConsistentStrings(string allowed, vector<string>& words) {
        int allowedChars = markCharactersOf(allowed);
        int answer = 0;
        
        for (string word : words) {
            int wordInWords = markCharactersOf(word);
            
            if ((wordInWords & allowedChars) == wordInWords)
                answer++;
        }
        
        return answer;
    }
};

Java

class Solution {
    public int markCharactersOf(String word) {
        int result = 0;
        
        for (char ch : word.toCharArray()) {
            int position = ch - 'a';
            result |= 1 << position;
        }
        
        return result;
    }
    
    public int countConsistentStrings(String allowed, String[] words) {
        int allowedChars = markCharactersOf(allowed);
        int answer = 0;
        
        for (String word : words) {
            int wordInWords = markCharactersOf(word);
            
            if ((wordInWords & allowedChars) == wordInWords)
                answer++;
        }
        
        return answer;
    }
}

C#

public class Solution {
    public int MarkCharactersOf(String word) {
        int result = 0;
        
        foreach (char ch in word.ToCharArray()) {
            int position = ch - 'a';
            result |= 1 << position;
        }
        
        return result;
    }
    
    public int CountConsistentStrings(string allowed, string[] words) {
        int allowedChars = MarkCharactersOf(allowed);
        int answer = 0;
        
        foreach (String word in words) {
            int wordInWords = MarkCharactersOf(word);
            
            if ((wordInWords & allowedChars) == wordInWords)
                answer++;
        }
        
        return answer;
    }
}