Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars. A string is good if it can be formed by characters from chars (each character can only be used once). Return the sum of lengths of all good strings in words.

Example 1:

Input: String[] words = { "cat", "bt", "hat", "tree" }; String chars = "atach";
Output: 6
Explanation: Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Algorithm:

Initialize an array arr of size 26 to represent the count of each lowercase letter in the chars string.
Iterate through each character in the chars string and update the count in the arr array.
Initialize a variable ans to store the total length of words that can be formed.
Iterate through each word in the words array.
1. Initialize an array arr_ of size 26 to represent the count of each lowercase letter in the current word s.
2. Initialize a boolean variable canMade to true.
3. Iterate through each character in the current word s and update the count in the arr_ array.
4. Check if there are enough available characters in chars to form the word. If not, set canMade to false and break out of the loop.
5. If canMade is still true after the inner loop, add the length of the current word s to the ans variable.
Return the total length of words that can be formed using the characters in chars (stored in the ans variable).

Code Implementation:

Java

class Solution {
    public static int countCharacters(String[] words, String chars) {
        int[] arr = new int[26];
        for (int i = 0; i < chars.length(); i++) {
            char c = chars.charAt(i);
            arr[c - 'a'] += 1;
        }

        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            int[] arr_ = new int[26];
            boolean canMade = true;
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                arr_[c - 'a'] += 1;
                if (arr[c - 'a'] < arr_[c - 'a']) {
                    canMade = false;
                    break;
                }
            }
            if (canMade) {
                ans += s.length();
            }
        }
        return ans;
    }

    // driver code
    public static void main(String[] args) {
        String[] words = { "cat", "bt", "hat", "tree" };
        String chars = "atach";

        int result = countCharacters(words, chars);
        System.out.println(result);
    }
}

Output:

Complexity Analysis:

Time Complexity: O(N + M * K),
1. The first loop that iterates through the characters in the chars string has a time complexity of O(N), where N is the length of the chars string.
2. The second loop iterates through each word in the words array, and for each word, it iterates through its characters. Let M be the maximum length of a word in the words array. Therefore, the time complexity of this part is O(M * K), where K is the number of words in the array.
Overall, the time complexity of the code is O(N + M * K).

Space Complexity:O(K),
1. The code uses an array arr of size 26 to store the count of characters in the chars string. Therefore, the space complexity for this part is O(26), which simplifies to O(1).
2. Inside the second loop, the code creates an array arr_ for each word, which is also of size 26. So, the space complexity for this part is O(26 * K), where K is the number of words in the array.
Therefore, the overall space complexity of the code is O(1 + 26 * K), which simplifies to O(K) since K is typically much smaller than the other parameters.

If you want to contribute such articles to solutions2coding.com please click here. Thank you!