algoadvance

Leetcode 1684. Count the Number of Consistent Strings

Problem Statement

1684. Count the Number of Consistent Strings

You are given a string allowed consisting of distinct characters and an array of strings words. A string is considered consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: String "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Clarifying Questions

  1. Q: Are the characters in the string allowed unique?
    • A: Yes, the problem statement specifies that allowed consists of distinct characters.
  2. Q: What is the length range of allowed and words?
    • A: The lengths are typically within reasonable constraints (e.g., 1 to 26 for allowed and lengths of individual strings in words can be various, but common problem constraints apply).
  3. Q: Can words contain empty strings?
    • A: While possible, the problem context generally implies non-empty strings for practical algorithm creation.

Strategy

  1. Data Structure Choice:
    • Utilize a set or a vector<bool> (size 26) to keep track of characters in allowed for O(1) membership checking.
  2. Algorithm Steps:
    • Convert allowed characters to a set or vector<bool>.
    • Initialize a counter to zero.
    • Iterate over each word in words and verify if all its characters exist in the allowed set/vector.
    • If consistent, increment the counter.
    • Return the counter’s value.
  3. Edge Cases:
    • If words is empty, return 0.
    • If there are no consistent strings, return 0.

Time Complexity

Code Implementation

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        unordered_set<char> allowedSet(allowed.begin(), allowed.end());
        int consistentCount = 0;
        
        for(const string& word : words) {
            bool isConsistent = true;
            for(char ch : word) {
                if(allowedSet.find(ch) == allowedSet.end()) {
                    isConsistent = false;
                    break;
                }
            }
            if(isConsistent) {
                ++consistentCount;
            }
        }
        
        return consistentCount;
    }
};

int main() {
    Solution solution;
    vector<string> words1 = {"ad","bd","aaab","baa","badab"};
    string allowed1 = "ab";
    cout << "The number of consistent strings: " << solution.countConsistentStrings(allowed1, words1) << endl;  // Output: 2

    vector<string> words2 = {"a","b","c","ab","ac","bc","abc"};
    string allowed2 = "abc";
    cout << "The number of consistent strings: " << solution.countConsistentStrings(allowed2, words2) << endl;  // Output: 7

    vector<string> words3 = {"cc","acd","b","ba","bac","bad","ac","d"};
    string allowed3 = "cad";
    cout << "The number of consistent strings: " << solution.countConsistentStrings(allowed3, words3) << endl;  // Output: 4

    return 0;
}

This implementation employs an unordered_set to store the allowed characters and then checks each word against this set to determine consistency, hence counting the number of consistent strings as required.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI