1160. Find Words That Can Be Formed by Characters

EasyArrayHash TableString

Problem Description

In this problem, we are given two inputs: an array of strings called words and a single string called chars. Our task is to determine which strings in the words array are "good". A "good" string is one that can be completely formed using the characters in chars. Each character in chars may only be used once when forming a word. After identifying all the "good" strings, we must calculate the sum of their lengths and return that sum as the result.

For example, if words = ["cat", "bt", "hat", "tree"] and chars = "atach", only "cat" and "hat" are "good" because they can be formed using the characters in chars without reusing a single character. The lengths of "cat" and "hat" are 3 and 3, respectively, so the sum is 6. The goal of the problem is to implement a function that can do this calculation for any given words and chars.

Intuition

The solution approach can be divided into the following steps:

Count Characters in chars: We first count the frequency of each character in the string chars. This helps us know how many times we can use a particular character while forming words.
Iterate Over words: Next, we loop through each string in words and count the frequency of each character in the current string (w).
Check if a Word Can be Formed: To determine if a word is "good", we compare character frequencies of the current word with those in chars. If for each character in the word, the count in chars is greater than or equal to the count in the word, the word is "good".
Calculate and Sum Lengths: For each "good" string found, we add its length to a running total, ans.
Return the Result: Once all words have been checked, return the accumulated sum of lengths.

The beauty of this approach lies in the efficient use of character counting, which allows us to verify if a word can be formed without having to repeatedly search for characters in chars. By using a Python Counter object, which is essentially a specialized dictionary for counting hashable objects, we perform the needed comparisons succinctly and efficiently. The all function in Python is then used to ensure that all character counts in the word meet the availability requirement in chars, which is a very intuitive way to check the condition for every character simultaneously.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Solution Approach

The implementation of the solution uses a Counter from Python's collections module, which is a specialized dictionary designed for counting hashable objects. The Counter data structure is ideal for tracking the frequency of elements in an iterable.

Here is a step-by-step breakdown of how the solution is implemented:

Create a Counter for chars: First, a Counter is created for the string chars. This Counter object, named cnt, will provide a dictionary-like structure where each key is a character from chars and its corresponding value is the number of occurrences of that character.
```
1cnt = Counter(chars)
```
Initialize an Answer Variable: An integer ans is initialized to zero, which will hold the sum of lengths of all "good" strings in the array words.
```
1ans = 0
```
Loop Through Each Word in words: We iterate over each word w in the words array. For each word, a new Counter is created to count the occurrences of characters in that word.
```
1for w in words:
2    wc = Counter(w)
```
Check if the Word is "Good": Using the all function, we check if every character c in the current word has a frequency count v that is less than or equal to its count in cnt. This ensures that each character required to form the word w is available in the quantity needed in chars.
```
1if all(cnt[c] >= v for c, v in wc.items()):
2    ans += len(w)
```
- If the condition is true for all characters, it means the word can be formed from the characters in chars, hence it is a "good" word. We add the length of the word to ans.
- We do not modify the original cnt Counter because we do not want to affect the counts for the subsequent iteration of words. Instead, we just use its values to check the wc counts.
Return the Total Length: After iterating through all the words, the total length of all "good" words is stored in ans, which we return.
```
1return ans
```

This algorithm has a time complexity that is dependent on the total number of characters in all words (O(N) where N is the total number of characters) since we are counting characters for each word and iterating over each character count. The space complexity is O(U) where U is the total number of unique characters in chars and all words since Counter objects need to keep track of each unique character and its count.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Example Walkthrough

Consider a small example where we have words = ["hello", "world", "loop"] and chars = "hloeldorw".

Step 1: Count Characters in chars: We count the frequency of each character:
```
1h:1, l:2, o:2, e:1, d:1, r:1, w:1
```
We have enough characters to potentially make the words "hello", "world", and "loop".
Step 2: Initialize an Answer Variable: We initialize ans to zero:
```
1ans = 0
```
Step 3: Iterate Over words: We iterate over each word:
- For "hello":
  - Count characters: h:1, e:1, l:2, o:1
  - We check each character against our chars count and see that we can form "hello" with chars. Since "hello" is a "good" word, we add its length (5) to ans:
```
1ans += 5   # ans = 5
```
- For "world":
  - Count characters: w:1, o:1, r:1, l:1, d:1
  - All characters are present in our chars count. "world" is also a "good" word, so we add its length (5) to ans:
```
1ans += 5   # ans = 10
```
- For "loop":
  - Count characters: l:1, o:2, p:1
  - We have only 2 'o's and 1 'l' in chars, not enough to form the word "loop", so we do not add anything to ans for this word.
Step 4: Return the Total Length: After processing all the words, the value of ans is 10 (5+5). This is the sum of lengths of all "good" words. We return this as the final answer:
```
1return ans   # ans = 10
```

The sum of lengths of all "good" words that can be formed by the given chars is 10 in this example.

Solution Implementation

1from collections import Counter  # Import the Counter class from the collections module
2
3class Solution:
4    def countCharacters(self, words: List[str], chars: str) -> int:
5        # Count the frequency of each character in the given string 'chars'
6        char_count = Counter(chars)
7        # Initialize answer to hold the total length of all words that can be formed
8        total_length = 0
9
10        # Iterate through each word in the list of words
11        for word in words:
12            # Count the frequency of each character in the current word
13            word_count = Counter(word)
14            # Check if the word can be formed by the chars in 'chars'
15            if all(char_count[char] >= count for char, count in word_count.items()):
16                total_length += len(word)  # If it can be formed, add the word's length to the total
17
18        # Return the total length of all words that can be formed
19        return total_length
20

1class Solution {
2    public int countCharacters(String[] words, String chars) {
3        // Array to store the frequency of each character in 'chars'
4        int[] charFrequency = new int[26];
5      
6        // Count the frequency of each character in 'chars'
7        for (int i = 0; i < chars.length(); ++i) {
8            charFrequency[chars.charAt(i) - 'a']++;
9        }
10      
11        // Variable to hold the total length of all words that can be formed
12        int totalLength = 0;
13      
14        // Iterate over each word in the array 'words'
15        for (String word : words) {
16            // Array to store the frequency of each character in the current word
17            int[] wordFrequency = new int[26];
18            // Flag to check if the current word can be formed
19            boolean canBeFormed = true;
20          
21            // Count the frequency of each character in the current word
22            for (int i = 0; i < word.length(); ++i) {
23                int index = word.charAt(i) - 'a';
24              
25                // If the character frequency exceeds that in 'chars', the word can't be formed
26                if (++wordFrequency[index] > charFrequency[index]) {
27                    canBeFormed = false;
28                    break; // Break out of the loop as the current word can't be formed
29                }
30            }
31          
32            // If the word can be formed, add its length to the totalLength
33            if (canBeFormed) {
34                totalLength += word.length();
35            }
36        }
37      
38        // Return the total length of all words that can be formed
39        return totalLength;
40    }
41}
42

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Determines the sum of lengths of all words that can be formed by characters in 'chars'
7    int countCharacters(vector<string>& words, string chars) {
8        // Frequency array for characters in 'chars'
9        int charCount[26] = {0};
10        // Fill the frequency array
11        for (char& ch : chars) {
12            ++charCount[ch - 'a'];
13        }
14      
15        int totalLength = 0; // This will hold the sum of lengths of words that can be formed
16
17        // Iterate over each word in the list
18        for (auto& word : words) {
19            // Frequency array for characters in the current word
20            int wordCount[26] = {0};
21            bool canFormWord = true; // Flag to check if the word can be formed
22          
23            // Check if each character in the word can be formed by the characters in 'chars'
24            for (char& ch : word) {
25                int index = ch - 'a';
26                // If the current character exceeds the frequency in 'chars', the word can't be formed
27                if (++wordCount[index] > charCount[index]) {
28                    canFormWord = false;
29                    break;
30                }
31            }
32
33            // If the word can be formed, add its length to the totalLength
34            if (canFormWord) {
35                totalLength += word.size();
36            }
37        }
38
39        return totalLength; // Return the total sum of lengths of all words that can be formed
40    }
41};
42

1function countCharacters(words: string[], chars: string): number {
2    // Function to get index of character in the alphabet array (0-25)
3    const getIndex = (char: string): number => char.charCodeAt(0) - 'a'.charCodeAt(0);
4
5    // Initialize an array to store the frequency of each character in 'chars'
6    const charCount = new Array(26).fill(0);
7    // Fill the charCount array with the frequency of each character in 'chars'
8    for (const char of chars) {
9        charCount[getIndex(char)]++;
10    }
11
12    // Initialize a variable to keep track of the total length of all valid words
13    let totalLength = 0;
14
15    // Iterate over each word in the 'words' array to check if it can be formed
16    for (const word of words) {
17        // Initialize an array to store the frequency of each character in the current word
18        const wordCount = new Array(26).fill(0);
19        // Flag to check if the current word can be formed
20        let canBeFormed = true;
21
22        // Iterate over each character in the word to update wordCount and check if it can be formed
23        for (const char of word) {
24            wordCount[getIndex(char)]++;
25            // If the character's frequency in word exceeds that in 'chars', set the flag to false
26            if (wordCount[getIndex(char)] > charCount[getIndex(char)]) {
27                canBeFormed = false;
28                break;
29            }
30        }
31
32        // If the word can be formed, add its length to the totalLength
33        if (canBeFormed) {
34            totalLength += word.length;
35        }
36    }
37
38    // Return the total length of all words that can be formed using 'chars'
39    return totalLength;
40}
41

Not Sure What to Study? Take the 2-min Quiz：

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed as follows:

The creation of the cnt counter from the chars string: this operation takes O(m), where m is the length of the chars string since we must count the frequency of each character in chars.
The for-loop iterates over each word in the words list. Let the length of the list be n and the average length of the words be k.
Inside the loop, a new counter wc is created for each word: this operation also has a complexity of O(k).
The all function checks if all characters in w have a count less or equal to their count in cnt. This operation is O(k) as it checks each character's count (up to the total character count of a word).

Since steps 3 and 4 are within the loop iteration, they will run n times, which makes that part of the algorithm O(n*k).

Summing these up, the total time complexity is O(m + n*k).

Space Complexity

The space complexity can be analyzed as follows:

The cnt counter for chars utilizes O(u) space, where u is the unique number of characters in chars.
The wc counter for each word similarly utilizes O(v) space in the worst case, where v is the unique number of characters in that word.
However, since wc is constructed for one word at a time, O(v) space will be reused for each word, and v is bounded by the fixed size of the alphabet (u), so we can consider O(u) space for the counters.

Given that space used by variables like ans and temporary variables in the iteration is negligible relative to the size of the input, the overall space complexity is dominated by the space required for the counters, which is O(u) where u is the number of unique letters in chars and is bounded by the size of the character set used (e.g., the English alphabet, which has a fixed size of 26).

Therefore, the space complexity is O(u).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1160. Find Words That Can Be Formed by Characters

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings