# Leetcode – Count the Number of Consistent Strings Solution

The “Count the Number of Consistent Strings” problem on Leetcode is an excellent exercise in string manipulation and set data structure. While the problem itself is straightforward, it opens up discussions on various Python techniques and data structures that can be employed for optimized solutions. In this article, we will walk you through multiple ways to tackle this problem, discuss their time and space complexities.

## Problem Statement

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.

#### Example:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2

Explanation: Strings “aaab” and “baa” are consistent since they only contain characters ‘a’ and ‘b’.

## Basic Approach: Nested Loops

The most naive approach is to use nested loops: one for iterating over each word in words and another for each character in the word. For each character, you can check if it exists in the allowed string.

#### Python Code

def countConsistentStrings(allowed, words):
count = 0
for word in words:
is_consistent = True
for char in word:
if char not in allowed:
is_consistent = False
break
if is_consistent:
count += 1
return count

### Time Complexity

The time complexity of this approach is O(m×n), where m is the average length of the strings in words, and n is the length of allowed.

## Optimized Approach: Using Set Data Structure

We can optimize the solution by converting the allowed string into a set. This conversion will make the lookup operation constant time, i.e., O(1).

#### Python 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

### Time Complexity

The time complexity is O(m×n) for the conversion to set and O(m) for traversing the words list, resulting in a total time complexity of O(m×n+m)≈O(m×n).

assert countConsistentStrings("ab", ["ad","bd","aaab","baa","badab"]) == 2
assert countConsistentStrings("cad", ["cc","acd","b","ba","bac","bad","ac","d"]) == 4