Count Words Obtained After Adding a Letter

Medium

Asked by:

14 views

Topics:

ArraysStringsBit Manipulation

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

Append any lowercase letter that is not present in the string to its end.
- For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
Rearrange the letters of the new string in any arbitrary order.
- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

1 <= startWords.length, targetWords.length <= 5 * 10⁴
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in `startWords` and `targetWords` contain duplicate letters? Are the words case-sensitive?
What are the maximum lengths of `startWords` and `targetWords`, and what is the maximum length of an individual word?
Are `startWords` and `targetWords` guaranteed to contain only lowercase English letters?
If a word in `targetWords` can be formed from multiple words in `startWords`, should I count it multiple times or only once?
If adding a letter to a `startWord` can result in the *same* `targetWord` by adding *different* letters at *different* positions, should that `targetWord` be counted only once?

Brute Force Solution

Approach

The brute force approach to this problem involves systematically checking every possible way to add a single letter to each start word to see if we can create a target word. We check each start word against all target words. It's like trying every key on a keyboard to see if it unlocks a door.

Here's how the algorithm would work step-by-step:

For each start word, consider adding every possible letter (a through z) in every possible position.
This creates a new set of potential target words based on the start word.
For each of these newly created potential target words, check if that new word exists in the list of target words.
If a new word is present in the target word list, increment the count of obtainable words.
After checking all possible additions for a start word, move to the next start word and repeat the process.
Finally, after examining every start word, return the total count of obtainable words.

Code Implementation

def count_words_obtained_after_adding_a_letter(start_words, target_words):
    count_of_obtainable_words = 0
    for start_word in start_words:
        for target_word in target_words:
            # If target word is not exactly one character longer, skip this comparison
            if len(target_word) != len(start_word) + 1:
                continue

            for index_to_add in range(len(start_word) + 1):
                for char_code in range(ord('a'), ord('z') + 1):
                    new_char = chr(char_code)
                    new_word = start_word[:index_to_add] + new_char + start_word[index_to_add:]

                    # Check if the newly created word matches the target word
                    if new_word == target_word:
                        count_of_obtainable_words += 1

                        # Break the inner loop if target word is found
                        break
                else:
                    continue

                # Break outer loop once target word has been found, since we have a match
                break
    return count_of_obtainable_words

Big(O) Analysis

Time Complexity

O(S * (L * 26 * (L+1)) * T) – Let S be the number of start words, T be the number of target words, and L be the maximum length of a start word. For each of the S start words, we iterate through all possible positions (L+1) and letters (26), creating a new word, taking O(L) for string creation/copying. This results in S * (L * 26 * (L+1)) potential new words. We then check if each of these potential words exists in the list of T target words using a linear search, taking O(T) time. Therefore the overall time complexity is O(S * (L * 26 * (L+1)) * T) which simplifies to O(S * L^2 * T).

Space Complexity

O(1) – The brute force approach, as described, primarily involves iterating and comparing strings. Although it generates potential new strings by adding letters, these are typically created and checked one at a time without being stored in a collection that scales with input size. It keeps a count of obtainable words. Thus the extra space required remains constant, regardless of the number of start words and target words.

Optimal Solution

Approach

The key is to represent each word as a unique number based on the letters it contains. Then, we can quickly check if adding a single letter to one word can create another word by doing simple numerical comparisons.

Here's how the algorithm would work step-by-step:

First, take each word and assign it a unique numerical code. Think of it like giving each letter a number and combining those numbers to create a unique code for each word.
Next, for each 'target' word, go through each of the 'start' words.
For each 'start' word, try adding one letter at every possible spot.
Convert the 'start' word with the added letter into a number code using the same method.
If this new number code matches the number code of the 'target' word, then it means the 'target' word can be created from the 'start' word by adding a letter.
Keep track of how many 'target' words can be created in this way.
Finally, return the total count of 'target' words that can be formed from the 'start' words.

Code Implementation

def count_words_obtained_after_adding_a_letter(start_words, target_words):
    def get_word_mask(word):
        mask = 0
        for char in word:
            mask |= (1 << (ord(char) - ord('a')))
        return mask

    start_word_masks = set()
    for start_word in start_words:
        start_word_masks.add(get_word_mask(start_word))

    count = 0
    for target_word in target_words:
        target_mask = get_word_mask(target_word)
        # Iterate through each possible letter to remove
        for i in range(len(target_word)): 
            temp_word = target_word[:i] + target_word[i+1:]
            temp_mask = get_word_mask(temp_word)

            # Check if the modified word's mask exists in start_word_masks
            if temp_mask in start_word_masks:
                count += 1
                break # Prevents double counting

    return count

Big(O) Analysis

Time Complexity

O(m * n * l) – Let m be the number of words in the startWords array, n be the number of words in the targetWords array, and l be the maximum length of a word. The outer loop iterates through each of the n words in targetWords. The inner loop iterates through each of the m words in startWords. Inside the inner loop, we try adding a letter at each possible position in the startWord, which takes at most l attempts. Converting each modified startWord to its numerical code and comparing it to the targetWord's code takes O(l) time in the worst case for hashing or character processing. Thus, the overall time complexity is O(m * n * l).

Space Complexity

O(M + N) – The algorithm implicitly uses space to store the unique numerical codes for each word in both the startWords and targetWords arrays. Let N be the number of words in startWords and M be the number of words in targetWords. Therefore, it will create two sets of size N and M respectively to store these unique codes. The dominant factor in space complexity is the storage of these unique codes for all words, leading to O(M + N) space complexity.

Edge Cases

Case	How to Handle
words or targetWords is null or empty	Return 0 if either input array is null or empty to avoid null pointer exceptions and incorrect results.
words or targetWords contain empty strings	Treat empty strings as invalid words and skip them to avoid unexpected behavior during character processing.
words or targetWords contain strings with non-lowercase characters	Convert all strings to lowercase to ensure case-insensitive comparison and handle mixed-case inputs correctly.
Very long strings in words or targetWords (potential performance issue)	Consider using a more efficient data structure or algorithm if the string length is excessively large to avoid exceeding time limits.
A word in targetWords can be formed by adding multiple different letters to a word in words.	The algorithm should correctly count these instances if they exist.
Integer overflow if using bit manipulation for character sets.	Use a larger integer type or alternative data structure if bit manipulation is used to prevent overflow when representing character sets.
Duplicate words in the input array 'words'.	The solution should handle duplicate 'words' correctly, potentially using a set to avoid double-counting valid counts.
Target word is the same as a word in words.	Ensure the target word is not counted if it is already present in the words array.

words or targetWords is null or empty

How to Handle:

Return 0 if either input array is null or empty to avoid null pointer exceptions and incorrect results.

words or targetWords contain empty strings

How to Handle:

Treat empty strings as invalid words and skip them to avoid unexpected behavior during character processing.

words or targetWords contain strings with non-lowercase characters

How to Handle:

Convert all strings to lowercase to ensure case-insensitive comparison and handle mixed-case inputs correctly.

Very long strings in words or targetWords (potential performance issue)

How to Handle:

Consider using a more efficient data structure or algorithm if the string length is excessively large to avoid exceeding time limits.

A word in targetWords can be formed by adding multiple different letters to a word in words.

How to Handle:

The algorithm should correctly count these instances if they exist.

Integer overflow if using bit manipulation for character sets.

How to Handle:

Use a larger integer type or alternative data structure if bit manipulation is used to prevent overflow when representing character sets.

Duplicate words in the input array 'words'.

How to Handle:

The solution should handle duplicate 'words' correctly, potentially using a set to avoid double-counting valid counts.

Target word is the same as a word in words.

How to Handle:

Ensure the target word is not counted if it is already present in the words array.