Introduction

In this blog post, we will explore how to solve the LeetCode problem "1160" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 only be used once). Return the sum of lengths of all good strings in words. Example 1: Input: words = ["cat","bt","hat","tree"], chars = "atach" Output: 6 Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6. Example 2: Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr" Output: 10 Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10. Constraints: 1 <= words.length <= 1000 1 <= words[i].length, chars.length <= 100 words[i] and chars consist of lowercase English letters.

Explanation

Here's the breakdown of the solution:

• Character Frequency Counting: Create a frequency map (dictionary) of characters in the chars string. This allows us to quickly check if we have enough of each character.

• Good String Check: For each word in words, iterate through its characters and check if the character exists in the chars frequency map and if we have enough of that character available. If a word is "good" (formable), add its length to the total sum.

• Efficiency: The approach avoids sorting or other costly operations. The frequency map lookups are O(1) on average.

• Complexity:

  • Runtime Complexity: O(n*m), where n is the number of words, and m is the average length of the words.
  • Storage Complexity: O(1), because frequency map is constant size (26 lowercase English letters).

Code

    def count_characters(words, chars):
    """
    Calculates the sum of lengths of "good" strings in 'words' that can be formed from 'chars'.

    Args:
        words: A list of strings.
        chars: A string.

    Returns:
        The sum of lengths of good strings.
    """

    char_counts = {}
    for char in chars:
        char_counts[char] = char_counts.get(char, 0) + 1

    total_length = 0
    for word in words:
        word_counts = {}
        is_good = True
        for char in word:
            word_counts[char] = word_counts.get(char, 0) + 1
            if char not in char_counts or word_counts[char] > char_counts[char]:
                is_good = False
                break

        if is_good:
            total_length += len(word)

    return total_length