Longest Common Prefix Between Adjacent Strings After Removals

Longest Common Prefix Between Adjacent Strings After Removals - Problem

Array String Medium

You are given an array of strings words. For each index i in the range [0, words.length - 1], perform the following steps:

1. Remove the element at index i from the words array.

2. Compute the length of the longest common prefix among all adjacent pairs in the modified array.

Return an array answer, where answer[i] is the length of the longest common prefix between the adjacent pairs after removing the element at index i. If no adjacent pairs remain or if none share a common prefix, then answer[i] should be 0.

Input & Output

Example 1 — Basic Case

$ Input: words = ["apple", "app", "application", "banana"]

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

💡 Note: Remove "apple": remaining ["app", "application", "banana"], max prefix = 3 (app-application). Remove "app": remaining ["apple", "application", "banana"], max prefix = 3 (apple-application). Remove "application": remaining ["apple", "app", "banana"], max prefix = 2 (apple-app). Remove "banana": remaining ["apple", "app", "application"], max prefix = 3 (app-application).

Example 2 — No Common Prefixes

$ Input: words = ["cat", "dog", "bird"]

› Output: [0, 0, 0]

💡 Note: No adjacent pairs share any common prefix characters, so all results are 0.

Example 3 — Two Elements

$ Input: words = ["test", "testing"]

› Output: [0, 0]

💡 Note: Removing either element leaves only one string, so no adjacent pairs exist.

Constraints

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

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to pre-compute all adjacent pair prefix lengths to avoid redundant calculations. The optimized approach calculates prefix lengths once, then efficiently handles each removal by identifying which pairs remain valid. Time: O(n × m + n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n² × m)	O(n)	For each removal, rebuild array and compute all adjacent prefix lengths
Pre-computed Adjacent Pairs	O(n × m + n²)	O(n)	Pre-compute all adjacent pair prefix lengths, then efficiently find maximum after each removal

Brute Force — Algorithm Steps

For each index i, create array without element i
For each adjacent pair in modified array, compute common prefix length
Return maximum prefix length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove Element

Create new array without element at index i

Check Adjacent Pairs

Compare each adjacent pair character by character

Find Maximum

Return the longest common prefix length found

Code -

solution.c — C

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

int* solution(char** words, int wordsSize, int* returnSize) {
    int* result = (int*)malloc(wordsSize * sizeof(int));
    *returnSize = wordsSize;
    
    for (int i = 0; i < wordsSize; i++) {
        // Create array without element at index i
        char** modified = (char**)malloc((wordsSize - 1) * sizeof(char*));
        int idx = 0;
        for (int j = 0; j < wordsSize; j++) {
            if (j != i) {
                modified[idx++] = words[j];
            }
        }
        
        if (wordsSize - 1 < 2) {
            result[i] = 0;
            free(modified);
            continue;
        }
        
        int maxPrefixLen = 0;
        
        // Check all adjacent pairs
        for (int j = 0; j < wordsSize - 2; j++) {
            int prefixLen = 0;
            char* str1 = modified[j];
            char* str2 = modified[j + 1];
            int len1 = strlen(str1);
            int len2 = strlen(str2);
            int minLen = len1 < len2 ? len1 : len2;
            
            // Find common prefix length
            for (int k = 0; k < minLen; k++) {
                if (str1[k] == str2[k]) {
                    prefixLen++;
                } else {
                    break;
                }
            }
            
            if (prefixLen > maxPrefixLen) {
                maxPrefixLen = prefixLen;
            }
        }
        
        result[i] = maxPrefixLen;
        free(modified);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for JSON array of strings
    char** words = (char**)malloc(100 * sizeof(char*));
    int wordsSize = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            words[wordsSize] = (char*)malloc((strlen(token) + 1) * sizeof(char));
            strcpy(words[wordsSize], token);
            wordsSize++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    int returnSize;
    int* result = solution(words, wordsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

For each of n removals, we check n-1 adjacent pairs, each comparison takes O(m) where m is average string length

⚠ Quadratic Growth

Space Complexity

O(n)

Extra space for modified array and result array

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 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 — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler