Count the Number of Consistent Strings — LeetCode #1684 (Easy)
Tags: Array, Hash Table, String, Bit Manipulation, Counting
Related patterns: Hash Map, Array
Brute Force approach
Time complexity: O(n * m). Space complexity: O(1).
The brute force approach checks each word individually to see if all its characters are present in the allowed string. It's straightforward but can be slow for larger inputs.
The time complexity is O(n * m) where n is the number of words and m is the average length of the words. We check each character of each word against the allowed string.
- Step 1: Initialize a counter to zero to keep track of consistent strings.
- Step 2: For each word in the words array, check each character of the word.
- Step 3: If all characters of the word are found in the allowed string, increment the counter.
- Step 4: Return the counter after checking all words.
1. allowed = 'ab', words = ['ad', 'bd', 'aaab', 'baa', 'badab']
2. Check 'ad': 'a' is in allowed, 'd' is not -> not consistent.
3. Check 'bd': 'b' is in allowed, 'd' is not -> not consistent.
4. Check 'aaab': 'a' is in allowed, 'b' is in allowed -> consistent, count = 1.
5. Check 'baa': 'b' is in allowed, 'a' is in allowed -> consistent, count = 2.
6. Check 'badab': 'b' is in allowed, 'a' is in allowed, 'd' is not -> not consistent.
Optimal Solution approach
Time complexity: O(n * m). Space complexity: O(k).
We can use a set to store the allowed characters for O(1) lookups, making the check for consistency much faster.
The time complexity remains O(n * m) but with faster character checks due to the set. Space complexity is O(k) where k is the number of distinct characters in allowed.
- Step 1: Convert the allowed string into a set of characters for fast lookup.
- Step 2: Initialize a counter to zero for consistent strings.
- Step 3: For each word in the words array, check if all characters are in the set of allowed characters.
- Step 4: Increment the counter for each consistent word.
- Step 5: Return the counter after processing all words.
1. allowed = 'ab', words = ['ad', 'bd', 'aaab', 'baa', 'badab']
2. allowed_set = {'a', 'b'}
3. Check 'ad': 'a' is in set, 'd' is not -> not consistent.
4. Check 'bd': 'b' is in set, 'd' is not -> not consistent.
5. Check 'aaab': 'a' is in set, 'b' is in set -> consistent, count = 1.
6. Check 'baa': 'b' is in set, 'a' is in set -> consistent, count = 2.
Key Insights
- Using a set for allowed characters allows for O(1) lookups, significantly speeding up the consistency checks.
- Brute force is often a good starting point, but understanding how to optimize can lead to better performance.
Common Mistakes
- Not using a set for allowed characters, leading to inefficient character checks.
- Overlooking edge cases, such as empty words or words with characters not in allowed.
Interview Tips
- Always start with a brute force solution to demonstrate your thought process.
- Explain your reasoning for optimizations clearly; interviewers appreciate understanding your thought process.
- Practice coding problems with varying constraints to get comfortable with different approaches.
