We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Words Obtained After Adding a Letter

Number: 2256

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given two arrays of strings, startWords and targetWords, determine how many strings in targetWords can be obtained by taking any string from startWords, appending exactly one letter (which is not already present in that string), and then rearranging its letters arbitrarily. The strings in both arrays have distinct characters, and the operation must add one letter to a valid start word before any rearrangement can be done.

Key Insights

  • Represent each string with a bit mask where each bit corresponds to a letter in the alphabet. This compact representation is efficient since the maximum word length is 26.
  • For every word in startWords, compute its bitmask and store it in a hash set for quick lookup.
  • For each target word, compute its bitmask and simulate the reverse operation by removing one letter at a time. Check if the resulting bitmask exists in the startWords set.
  • If a match is found, it indicates that the target word can be constructed by appending the removed letter to the corresponding start word.

Space and Time Complexity

Time Complexity: O(m * L + n * L), where m is the number of startWords, n is the number of targetWords, and L is the average length of a word (maximum 26).
Space Complexity: O(m) for storing the bit masks of startWords.

Solution

The algorithm leverages bit manipulation to represent each word as a 26-bit integer. For startWords, every word is converted to its bitmask and stored in a set. For each target word, we generate its bitmask and try removing each letter (i.e., toggle off one bit at a time) to form a modified bitmask. If the modified bitmask exists in the set of startWords, then we have found a valid transformation. This approach avoids the overhead of generating permutations while taking full advantage of the small fixed alphabet size.

Code Solutions

# Function to convert a word into its bitmask representation.
def bitmask_for_word(word):
    mask = 0
    for char in word:
        mask |= 1 << (ord(char) - ord('a'))
    return mask

def countConstructibleWords(startWords, targetWords):
    startMasks = set()
    # Convert startWords to bitmask representations and store them in a set.
    for word in startWords:
        startMasks.add(bitmask_for_word(word))
    
    count = 0
    # For each target word, try to reverse the operation by removing one letter.
    for word in targetWords:
        targetMask = bitmask_for_word(word)
        for char in word:
            # Remove the current letter and check if the resulting mask exists.
            modifiedMask = targetMask ^ (1 << (ord(char) - ord('a')))
            if modifiedMask in startMasks:
                count += 1
                break  # Stop checking after finding one valid transformation.
    return count

# Example usage:
startWords = ["ant", "act", "tack"]
targetWords = ["tack", "act", "acti"]
print(countConstructibleWords(startWords, targetWords))
← Back to All Questions