Leetcode 1684: Count the Number of Consistent Strings

Input: The input consists of a string `allowed` and an array `words`.

Example: allowed = 'abc', words = ['a', 'ab', 'abc', 'abcd', 'bc']

Constraints:

• 1 <= words.length <= 10^4

• 1 <= allowed.length <= 26

• 1 <= words[i].length <= 10

• The characters in allowed are distinct.

• words[i] and allowed contain only lowercase English letters.

Output: Return the number of consistent strings in the array `words`.

Example: Output: 5

Constraints:

Goal: The goal is to count how many strings in the array `words` consist solely of characters from the `allowed` string.

Steps:

• Initialize a variable to store the count of consistent strings.

• Create a boolean array to track which characters are allowed.

• Iterate through each string in `words` and check if all its characters are present in the `allowed` string.

• For each word, if any character is not in the `allowed` string, it is not consistent, so skip counting it.

• Return the count of consistent strings.

Goal: The input string `allowed` and the array `words` must satisfy the following constraints:

Steps:

• 1 <= words.length <= 10^4

• 1 <= allowed.length <= 26

• 1 <= words[i].length <= 10

• The characters in allowed are distinct.

• words[i] and allowed contain only lowercase English letters.

Assumptions:

• The string `allowed` contains distinct lowercase English characters.

• All input strings and arrays will be valid as per the constraints.

• Input: Input: allowed = 'abc', words = ['a', 'ab', 'abc', 'abcd', 'bc']

• Explanation: All strings are consistent because they contain only characters from 'abc'.

Approach: To solve this problem, we need to check if each string in the array `words` contains only characters that are present in the `allowed` string.

Observations:

• The `allowed` string has a small length (at most 26 characters), so we can use a boolean array to efficiently check for membership.

• We need to check each word in `words` for consistency by checking if every character in the word exists in the `allowed` string.

Steps:

• Initialize a boolean array to store whether each character from 'a' to 'z' is in `allowed`.

• For each word in `words`, check each character to see if it is in `allowed` using the boolean array.

• If all characters in a word are in `allowed`, increment the count.

• Return the count of consistent strings.

Empty Inputs:

• If `words` is empty, the answer should be 0.

Large Inputs:

• For large arrays of strings (`words.length` up to 10^4), ensure the solution is efficient.

Special Values:

• If `allowed` is empty, no words can be consistent.

Constraints:

• The solution should handle the maximum input size within reasonable time limits.

int countConsistentStrings(string allowed, vector<string>& words) {
    int res = words.size();
    bool mp[26] = {};
    for (char c: allowed) mp[c - 'a'] = true;
    for (string word: words) {
        for (char c: word) if (!mp[c - 'a']) {
            res--;
            break;
        }
    }
    return res;        
}

1 : Function Definition

int countConsistentStrings(string allowed, vector<string>& words) {

Define the function 'countConsistentStrings' that takes an allowed string and a vector of words as input and returns the count of words consisting only of allowed characters.

2 : Variable Initialization

    int res = words.size();

Initialize the result variable 'res' to the number of words in the 'words' vector, as each word is initially assumed to be consistent.

3 : Array Initialization

    bool mp[26] = {};

Declare and initialize a boolean array 'mp' of size 26 to track which characters are allowed, where each index corresponds to a letter of the alphabet.

4 : Loop Through Allowed Characters

    for (char c: allowed) mp[c - 'a'] = true;

Loop through each character in the 'allowed' string and mark its corresponding index in the 'mp' array as 'true' to indicate that the character is allowed.

5 : Loop Through Words

    for (string word: words) {

Start a loop to process each word in the 'words' vector.

6 : Loop Through Word Characters

        for (char c: word) if (!mp[c - 'a']) {

Loop through each character of the current word and check if it is allowed by referencing the 'mp' array. If a character is not allowed, exit the loop.

7 : Decrement Result

            res--;

If a character in the word is not allowed, decrement the 'res' variable since this word is not consistent with the allowed characters.

8 : Break Loop

            break;

Exit the inner loop once an invalid character is found in the word to stop further processing of that word.

9 : Return Statement

    return res;

Return the final value of 'res', which represents the count of words that are consistent with the allowed characters.

Best Case: O(n * m), where n is the number of words and m is the length of the longest word.

Average Case: O(n * m)

Worst Case: O(n * m)

Description: The time complexity is O(n * m), where n is the number of words and m is the length of the longest word.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) since we only use a fixed-size boolean array of length 26.

Leetcode 1684: Count the Number of Consistent Strings

Explore →