Leetcode Daily Question 12/09/2024 - 1684. Count the Number of Consistent Strings

Problem Description:

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

from typing import List
class Solution:
  def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
    result = 0 
    allowed_set = set(allowed)
    for word in words:
      for char in word:
        if char not in allowed_set:
          break
      else:
        result += 1
    
    return result

Explanation:

We can brute force this question by checking if every string in words fit the criteria.

To do this efficiently we can make allowed into a set to make the look up constant time.

Then when we iterate over the words, we check if every character in the word belongs to allowed_set, if not then we break.

def countConsistentStrings(allowed,words):
  result = 0 
  allowed_set = set(allowed)
  
  for word in words:
    if all(char in allowed_set for char in word):
      result += 1
  
  return result

The all() method check if every character in the word belongs to allowed_set and breaks if we encounter a disallowed character.

On that note, there is another method to do this with the less-seen for-else loop.

A for-else loop works by checking if the for loop has been completed. If it has, then we can go to the else clause.

all() is a built-in Python function, it incurs a function call overhead, as it takes a generator expression or an iterable. Although this overhead is small, it can add up when you call all() many times, especially for large input sizes.

Whereas, for-else loop avoid this overhead, making it faster practically.

def countConsistentStrings(allowed, words):
  result = 0
  allowed_set = set(allowed)
  
  for word in words:
    for char in word:
      if char not in allowed_set:
        break
    else:
        result += 1
  
  return result

The time complexity for both method is the same, O(k + n * m). Where k is the length of allowed, n is length of words, and m is average word length.

The space complexity is O(k).

The full solution can be found near the top of the page. Note that I have attached only the for-else loop solution.