Longest Common Prefix of K Strings After Removal

Longest Common Prefix of K Strings After Removal - Problem

You are given an array of strings words and an integer k. For each index i in the range [0, words.length - 1], find the length of the longest common prefix among any k strings (selected at distinct indices) from the remaining array after removing the i-th element.

Return an array answer, where answer[i] is the answer for the i-th element. If removing the i-th element leaves the array with fewer than k strings, answer[i] is 0.

Input & Output

Example 1 — Basic Case

$ Input: words = ["cat","car","card","care"], k = 2

› Output: [3,3,2,3]

💡 Note: Remove "cat": best 2-combination is ["car","card"] or ["car","care"] with prefix "car" (length 3). Remove "car": best is ["card","care"] with prefix "car" (length 3). Remove "card": best is ["cat","car"] with prefix "ca" (length 2). Remove "care": best is ["car","card"] with prefix "car" (length 3).

Example 2 — Insufficient Strings

$ Input: words = ["ab","bc"], k = 3

› Output: [0,0]

💡 Note: After removing any element, only 1 string remains, but k=3 is required, so answer is [0,0].

Example 3 — No Common Prefix

$ Input: words = ["abc","def","ghi"], k = 2

› Output: [0,0,0]

💡 Note: No two strings share a common prefix, so longest common prefix length is 0 for all removals.

Constraints

2 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 100
1 ≤ k ≤ words.length
words[i] consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings and target count k

Process

For each removal, find best k-combination prefix

Output

Array of maximum prefix lengths

Key Takeaway

🎯 Key Insight: Use trie structure to efficiently find longest common prefixes without checking all combinations

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to use a trie data structure to efficiently find common prefixes without generating all k-combinations. The optimal approach builds a trie with count tracking, temporarily removes counts for excluded words, then performs DFS to find the deepest node with k available paths. Time: O(n × m × L), Space: O(n × L).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Combinations	O(n × C(n-1,k) × m)	O(C(n-1,k))	For each removal, check all k-combinations for longest common prefix
Trie-Based Optimization	O(n × m × L)	O(n × L)	Use trie structure to efficiently find common prefixes without generating all combinations

Brute Force - Check All Combinations — Algorithm Steps

Step 1: For each index i, create array without words[i]
Step 2: Generate all combinations of k strings from remaining array
Step 3: Find longest common prefix for each combination
Step 4: Return maximum prefix length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove Element

Remove words[i] from array

Generate Combinations

Create all possible k-combinations from remaining strings

Find Max Prefix

Calculate longest common prefix for each combination

Code -

solution.c — C

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

#define MAX_WORDS 100
#define MAX_LEN 1000

int getCommonPrefixLength(char words[][MAX_LEN], int count) {
    if (count == 0) return 0;
    
    int minLen = strlen(words[0]);
    for (int i = 1; i < count; i++) {
        int len = strlen(words[i]);
        if (len < minLen) minLen = len;
    }
    
    int prefixLen = 0;
    for (int i = 0; i < minLen; i++) {
        char ch = words[0][i];
        int allMatch = 1;
        for (int j = 1; j < count; j++) {
            if (words[j][i] != ch) {
                allMatch = 0;
                break;
            }
        }
        if (allMatch) {
            prefixLen++;
        } else {
            break;
        }
    }
    
    return prefixLen;
}

void getCombinations(char remaining[][MAX_LEN], int n, int k, int start, char current[][MAX_LEN], int currentSize, int* maxPrefixLen) {
    if (currentSize == k) {
        int prefixLen = getCommonPrefixLength(current, k);
        if (prefixLen > *maxPrefixLen) {
            *maxPrefixLen = prefixLen;
        }
        return;
    }
    
    for (int i = start; i < n; i++) {
        strcpy(current[currentSize], remaining[i]);
        getCombinations(remaining, n, k, i + 1, current, currentSize + 1, maxPrefixLen);
    }
}

int* solution(char words[][MAX_LEN], int wordsSize, int k, int* returnSize) {
    *returnSize = wordsSize;
    int* answer = (int*)malloc(wordsSize * sizeof(int));
    
    for (int i = 0; i < wordsSize; i++) {
        // Create array without words[i]
        char remaining[MAX_WORDS][MAX_LEN];
        int remainingSize = 0;
        
        for (int j = 0; j < wordsSize; j++) {
            if (j != i) {
                strcpy(remaining[remainingSize], words[j]);
                remainingSize++;
            }
        }
        
        // If not enough strings left
        if (remainingSize < k) {
            answer[i] = 0;
            continue;
        }
        
        int maxPrefixLen = 0;
        char current[MAX_WORDS][MAX_LEN];
        
        // Check all combinations of k strings
        getCombinations(remaining, remainingSize, k, 0, current, 0, &maxPrefixLen);
        
        answer[i] = maxPrefixLen;
    }
    
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array of strings (simplified)
    char words[MAX_WORDS][MAX_LEN];
    int wordsSize = 0;
    
    char* token = strtok(line, "[\"]");
    while (token != NULL && wordsSize < MAX_WORDS) {
        if (strlen(token) > 0 && strcmp(token, ",") != 0 && strcmp(token, " ") != 0) {
            // Remove quotes and whitespace
            char* start = token;
            while (*start == ' ' || *start == '"') start++;
            char* end = start + strlen(start) - 1;
            while (end > start && (*end == ' ' || *end == '"' || *end == ',' || *end == '\n')) end--;
            *(end + 1) = '\0';
            
            if (strlen(start) > 0) {
                strcpy(words[wordsSize], start);
                wordsSize++;
            }
        }
        token = strtok(NULL, "[\"]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(words, wordsSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × C(n-1,k) × m)

For each of n removals, check C(n-1,k) combinations, each taking O(m) time to find common prefix

✓ Linear Growth

Space Complexity

O(C(n-1,k))

Space to store all k-combinations

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

890 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

Brute Force - Check All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler