algoadvance

Leetcode 1160. Find Words That Can Be Formed by Characters

Problem Statement:

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 be used only once). Return the sum of lengths of all good strings in words.

Example:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" which has a length of 3+3=6.

Clarifying Questions:

1. Can characters be reused for different words?
   • Yes, the characters in chars can be reused for different words, but within a single word, a character from chars can only be used as many times as it appears in chars.
2. What should be done for an empty words array or chars string?
   • If words is empty, return 0. If chars is empty, no word can be formed, so return 0 as well.
3. Are all characters lowercase English letters (a-z) only?
   • Yes, the problem statement ensures that all characters are lowercase English letters.

Strategy:

1. Count Character Frequencies:
   • First, we will count the frequency of each character in chars using an array or unordered_map.
2. Check Each Word:
   • For each word in words, we will create a frequency count, and check if it can be formed using characters in chars.
3. Sum Lengths:
   • If a word can be formed, add its length to the sum.

Code:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

int countCharacters(vector<string>& words, string chars) {
    // Create a frequency count for chars
    unordered_map<char, int> charsCount;
    for (char ch : chars) {
        charsCount[ch]++;
    }

    int totalLength = 0;
    
    for (const string& word : words) {
        // Create a frequency count for the current word
        unordered_map<char, int> wordCount;
        for (char ch : word) {
            wordCount[ch]++;
        }

        // Check if the word can be formed by chars
        bool canBeFormed = true;
        for (const auto& pair : wordCount) {
            char ch = pair.first;
            int freq = pair.second;
            if (charsCount[ch] < freq) {
                canBeFormed = false;
                break;
            }
        }

        // If the word can be formed, add its length to totalLength
        if (canBeFormed) {
            totalLength += word.length();
        }
    }

    return totalLength;
}

int main() {
    vector<string> words = {"cat", "bt", "hat", "tree"};
    string chars = "atach";
    cout << "Output: " << countCharacters(words, chars) << endl; // Output: 6
    return 0;
}

Time Complexity:

• Preprocessing:
  • Counting characters in chars takes O(n), where n is the length of chars.
• Checking Words:
  • For each word in words, creating the frequency count of the word and checking against charsCount takes O(m) time, where m is the length of the word.
  • Therefore, for all words, the time complexity is O(W * L), where W is the number of words and L is the average length of the words.
• Overall:
  • The overall time complexity is O(n + W * L).

This solution is efficient for the problem constraints and should work well for typical input sizes.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?