Leetcode – Count the Number of Consistent Strings Solution

Spread the love

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).

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

Conclusion

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.

Leave a Reply