Count Words Obtained After Adding a Letter

Count Words Obtained After Adding a Letter - Problem

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: 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.

Input & Output

Example 1 — Basic Transformation

$ Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]

› Output: 2

💡 Note: "tack" can be formed from "act" by adding 'k' and rearranging. "act" can be formed from "act" by adding any missing letter then removing it (impossible), but "act" can be formed from "ant" by adding 'c' and rearranging. "acti" can be formed from "act" by adding 'i'. Total: 2 words can be transformed.

Example 2 — No Valid Transformations

$ Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]

› Output: 1

💡 Note: "abc" can be formed from "ab" by adding 'c'. "abcd" cannot be formed from any start word as it would require adding 2+ letters. Total: 1 word can be transformed.

Example 3 — Multiple Start Options

$ Input: startWords = ["g","go"], targetWords = ["og"]

› Output: 1

💡 Note: "og" can be formed from "g" by adding 'o' and rearranging to get "go", then rearranging to "og". Total: 1 word can be transformed.

Constraints

1 ≤ startWords.length, targetWords.length ≤ 5 × 10⁴
1 ≤ startWords[i].length, targetWords[i].length ≤ 10
startWords[i] and targetWords[i] consist of lowercase English letters only
No string in startWords is a prefix of any other string in startWords

Visualization

Tap to expand

Understanding the Visualization

Input

Start words: ['ant', 'act'], Target words: ['tack', 'acti']

Transform

Add one missing letter + rearrange = new word

Count

Count how many targets can be formed

Key Takeaway

🎯 Key Insight: A target word can be formed if it has exactly one more unique character than any start word

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is that we can transform a start word to a target word if and only if the target has exactly one more unique character than the start word. The optimal approach uses bit masks to represent character sets, allowing O(1) comparisons instead of string sorting. Time: O(n×k + m×k), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sorted String Signatures	O(n × k log k + m × k²)	O(n × k)	Convert words to sorted signatures for efficient comparison
Bit Mask Optimization	O(n × k + m × k)	O(n)	Use bit masks to represent character sets for O(1) comparisons
Brute Force with Letter Addition	O(n × m × 26 × k log k)	O(k)	For each target word, try adding each missing letter to every start word

Sorted String Signatures — Algorithm Steps

Create a set of sorted signatures for all start words
For each target word, try removing each character
Check if the resulting sorted string exists in start word signatures
Count successful matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Pre-process

Sort all start words: 'ab'→'ab', 'ba'→'ab'

Try Removals

For target 'cab', try removing 'c'→'ab', 'a'→'bc', 'b'→'ac'

Lookup

Check if 'ab' exists in signature set - Found!

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_WORD_LEN 20

char startSignatures[MAX_WORDS][MAX_WORD_LEN];
int startCount = 0;

int compareChar(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

bool findSignature(char* sig) {
    for (int i = 0; i < startCount; i++) {
        if (strcmp(startSignatures[i], sig) == 0) {
            return true;
        }
    }
    return false;
}

int solution(char startWords[][MAX_WORD_LEN], int startSize, char targetWords[][MAX_WORD_LEN], int targetSize) {
    // Create sorted signatures for start words
    startCount = startSize;
    for (int i = 0; i < startSize; i++) {
        strcpy(startSignatures[i], startWords[i]);
        int len = strlen(startSignatures[i]);
        qsort(startSignatures[i], len, sizeof(char), compareChar);
    }
    
    int count = 0;
    
    for (int t = 0; t < targetSize; t++) {
        char target[MAX_WORD_LEN];
        strcpy(target, targetWords[t]);
        int targetLen = strlen(target);
        bool found = false;
        
        // Try removing each character from target
        for (int i = 0; i < targetLen && !found; i++) {
            char remaining[MAX_WORD_LEN];
            int pos = 0;
            
            // Create word without character at position i
            for (int j = 0; j < targetLen; j++) {
                if (j != i) {
                    remaining[pos++] = target[j];
                }
            }
            remaining[pos] = '\0';
            
            qsort(remaining, pos, sizeof(char), compareChar);
            
            if (findSignature(remaining)) {
                found = true;
            }
        }
        
        if (found) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char startWords[MAX_WORDS][MAX_WORD_LEN];
    char targetWords[MAX_WORDS][MAX_WORD_LEN];
    int startSize = 0, targetSize = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    char *token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= 'a' && token[0] <= 'z') {
            strcpy(startWords[startSize++], token);
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= 'a' && token[0] <= 'z') {
            strcpy(targetWords[targetSize++], token);
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    printf("%d\n", solution(startWords, startSize, targetWords, targetSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k log k + m × k²)

n start words × k log k sorting + m target words × k characters × k sorting

⚡ Linearithmic

Space Complexity

O(n × k)

Hash set storing n sorted start word strings, each of length k

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~25 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sorted String Signatures — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler