algoadvance

Given a string allowed consisting of distinct characters and an array of strings words, return the number of consistent strings in the array. A string is consistent if all characters in the string appear in the string allowed.

Clarifying Questions

1. Can allowed contain non-alphabetic characters?
   • According to the problem constraints and common sense, allowed contains distinct alphabetic characters.
2. Are the characters in words case-sensitive?
   • Yes, they are case-sensitive, and thus ‘A’ and ‘a’ would be treated as different characters.
3. Is there a limit to the length of allowed or the array words?
   • Generally, problems have reasonable constraints within typical coding interview standards (e.g., length of allowed <= 100, number of words <= 1000, total characters in words <= 10000).

Strategy

1. Convert the allowed string into a set of characters for O(1) average-time complexity membership checks.
2. Iterate through each word in the words list and check if all characters in the word are present in the allowed_set.
3. Maintain a count of the consistent strings and return the final count.

Code

def countConsistentStrings(allowed, words):
    allowed_set = set(allowed)
    count = 0

    for word in words:
        if all(char in allowed_set for char in word):
            count += 1

    return count

Explanation

1. Convert allowed to Set: We convert the string allowed into a set allowed_set to leverage the average O(1) lookup time for determining if a character is in allowed.

2. Iterate Over Each Word:
   • For each word in the words array, we use a generator expression within all() to check if every character in the word is present in allowed_set.
   • If the word passes the check, it is considered consistent, and we increment our count by 1.
3. Return Count: Finally, we return the count of consistent strings.

Time Complexity

• Converting allowed to a set: O(L), where L is the length of allowed.
• Checking each word: Let W be the total number of words and N be the maximum length of a word.
  • Checking if all characters of a word are in the set takes O(N) in the worst case.
  • Therefore, the overall time for checking all words is O(W * N).

In summary, the total time complexity is O(L + W * N). Here, L is typically much smaller than W * N, so the dominating term is W * N.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?