algoadvance

Leetcode 1684. Count the Number of Consistent Strings

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

Clarifying Questions

  1. Can the allowed string be empty?
    • No, the problem specifies that the allowed string consists of distinct characters, so it cannot be empty.
  2. What are the constraints on the length of allowed and words?
    • The length of allowed is in the range [1, 26].
    • The length of words is in the range [1, 10^4].
    • The length of each word in words is in the range [1, 10^4].
    • words[i] and allowed consist of only lowercase English letters.

Strategy

  1. Utilize a Set for allowed Characters:
    • Convert the allowed string into a set of characters for faster lookup.
  2. Iterate Over Each Word:
    • For each word in words, check if all characters are in the allowed set.
  3. Count Consistent Strings:
    • Maintain a counter to keep track of words where all characters are in the allowed set.

Code Implementation

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        // Convert the allowed string into a set for fast lookup
        Set<Character> allowedSet = new HashSet<>();
        for (char ch : allowed.toCharArray()) {
            allowedSet.add(ch);
        }
        
        int count = 0; // Initialize the counter for consistent strings
        
        // Iterate through each word in the array
        for (String word : words) {
            boolean isConsistent = true;
            for (char ch : word.toCharArray()) {
                if (!allowedSet.contains(ch)) {
                    isConsistent = false;
                    break;
                }
            }
            if (isConsistent) {
                count++;
            }
        }
        
        return count; // Return the number of consistent strings
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countConsistentStrings("ab", new String[]{"ad","bd","aaab","baa","badab"})); // Output: 2
        System.out.println(sol.countConsistentStrings("abc", new String[]{"a","b","c","ab","ac","bc","abc"})); // Output: 7
        System.out.println(sol.countConsistentStrings("cad", new String[]{"cc","acd","b","ba","bac","bad","ac","d"})); // Output: 4
    }
}

Time Complexity

Overall, the time complexity is O(n + m*k), which is efficient given the problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI