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.
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
Return the number of consistent strings in the array
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
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
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
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).
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
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).
Testing Your Solution
Before submitting your code, you should test it against various test cases to ensure its correctness.
assert countConsistentStrings("ab", ["ad","bd","aaab","baa","badab"]) == 2 assert countConsistentStrings("abc", ["a","b","c","ab","ac","bc","abc"]) == 7 assert countConsistentStrings("cad", ["cc","acd","b","ba","bac","bad","ac","d"]) == 4
The “Count the Number of Consistent Strings” problem, although straightforward, provides a great opportunity to practice working with Python sets and string manipulation. As we saw, using sets can offer an optimized solution with constant-time lookup operations. Understanding these Python data structures and their time complexities is crucial when tackling more complex problems.