LeetCode 3485 - Longest Common Prefix of K Strings After Removal
This problem asks us to calculate the longest common prefix (LCP) among any k strings from a list of strings, after removing each string in turn. Specifically, for each index i, we remove words[i] from the array, then find the longest prefix shared by any k remaining strings.
Difficulty: 🔴 Hard
Topics: Array, String, Trie
Solution
Problem Understanding
This problem asks us to calculate the longest common prefix (LCP) among any k strings from a list of strings, after removing each string in turn. Specifically, for each index i, we remove words[i] from the array, then find the longest prefix shared by any k remaining strings. The output is an array where each position i contains this value.
The input consists of words, an array of lowercase strings, and an integer k. Each string can have up to 10,000 characters, and the total combined length of all strings does not exceed 100,000. This prevents us from doing naive pairwise comparisons for all subsets because words.length can be as large as 100,000.
The output is an integer array representing the maximum prefix length for any k strings after removing each word. If removing a word leaves fewer than k strings, the answer is automatically 0.
Important edge cases include when k is equal to the total number of words, when all strings are identical, when all strings are completely distinct, or when removing a word reduces the frequency of the most common prefix below k.
Approaches
Brute Force
The naive approach is straightforward. For each index i, remove words[i], generate all combinations of size k from the remaining array, and compute the LCP for each combination. Keep track of the maximum LCP found.
While this approach is correct, it is exponentially slow because generating all combinations of k from n-1 strings takes O(C(n-1, k)), and calculating the LCP for each combination requires iterating over the string characters. With n up to 100,000, this is infeasible.
Optimal Approach
The key insight is that the LCP of k strings is determined by the most common prefixes of length l across the array. We can use a Trie to count how many strings share each prefix. In a Trie, each node can track the frequency of strings passing through it. The LCP of any k strings corresponds to the deepest node in the Trie that has frequency ≥ k.
To handle the removal of each word efficiently, we can first compute the Trie frequencies for all strings. Then, for each word, we simulate decrementing its path in the Trie, recompute the longest prefix of at least k strings, and restore it. This reduces the problem from combinatorial explosion to linear processing of the Trie nodes along the word paths.
The Trie ensures we process characters only once per string instead of generating combinations.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n choose k * L) | O(L * k) | Generate all combinations and compute LCPs; infeasible for large n |
| Optimal | O(N * L) | O(N * L) | Use Trie with frequency counts, decrement paths per removal to compute LCP efficiently |
Where N is the number of strings and L is the average string length.
Algorithm Walkthrough
-
Build a Trie: Insert every word in the array into a Trie. Each node stores
count- the number of strings passing through that node. -
Compute initial LCP counts: For the full array, traverse the Trie. For each node, if its count ≥ k, update a global
max_prefix_lengthalong the path to that node. -
Compute answers for each removal:
-
For index
i, takewords[i]. -
Traverse the Trie along the word path, decrementing the
countat each node by 1. -
After decrement, traverse the Trie to find the deepest node with count ≥ k. The depth of this node is
answer[i]. -
Restore the Trie by incrementing the counts along the path of
words[i]. -
Return the array of answers after processing all indices.
Why it works: Each Trie node correctly counts how many words pass through it. By decrementing counts for a removed word, we simulate the removal without copying arrays or generating combinations. The deepest node with count ≥ k represents the longest prefix that is common to at least k remaining strings.
Python Solution
from typing import List
from collections import defaultdict
class TrieNode:
def __init__(self):
self.children = defaultdict(TrieNode)
self.count = 0
class Solution:
def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
if k > len(words):
return [0] * len(words)
root = TrieNode()
# Build Trie
for word in words:
node = root
for ch in word:
node = node.children[ch]
node.count += 1
def compute_lcp():
max_len = 0
stack = [(root, 0)]
while stack:
node, depth = stack.pop()
if node.count >= k:
max_len = max(max_len, depth)
for child in node.children.values():
stack.append((child, depth + 1))
return max_len
answer = []
for word in words:
# Decrement counts along the path
node = root
for ch in word:
node = node.children[ch]
node.count -= 1
# Compute LCP after removal
answer.append(compute_lcp())
# Restore counts
node = root
for ch in word:
node = node.children[ch]
node.count += 1
return answer
The Python solution builds a Trie where each node counts how many words pass through. For each word removal, it temporarily decrements counts along its path, computes the deepest node with count ≥ k, and restores the counts.
Go Solution
package main
func longestCommonPrefix(words []string, k int) []int {
type TrieNode struct {
children map[byte]*TrieNode
count int
}
root := &TrieNode{children: make(map[byte]*TrieNode)}
// Build Trie
for _, word := range words {
node := root
for i := 0; i < len(word); i++ {
ch := word[i]
if node.children[ch] == nil {
node.children[ch] = &TrieNode{children: make(map[byte]*TrieNode)}
}
node = node.children[ch]
node.count++
}
}
var computeLCP func() int
computeLCP = func() int {
maxLen := 0
stack := []struct {
node *TrieNode
depth int
}{{root, 0}}
for len(stack) > 0 {
last := stack[len(stack)-1]
stack = stack[:len(stack)-1]
node := last.node
depth := last.depth
if node.count >= k {
if depth > maxLen {
maxLen = depth
}
for _, child := range node.children {
stack = append(stack, struct {
node *TrieNode
depth int
}{child, depth + 1})
}
}
}
return maxLen
}
answer := make([]int, len(words))
for idx := range words {
node := root
for i := 0; i < len(words[idx]); i++ {
ch := words[idx][i]
node = node.children[ch]
node.count--
}
answer[idx] = computeLCP()
node = root
for i := 0; i < len(words[idx]); i++ {
ch := words[idx][i]
node = node.children[ch]
node.count++
}
}
return answer
}
In Go, the implementation uses explicit maps for children. The logic mirrors Python: decrement counts, compute LCP, restore counts. Go-specific considerations include using map[byte]*TrieNode and handling slices for stack traversal.
Worked Examples
Example 1: words = ["jump","run","run","jump","run"], k = 2
| Removal | Remaining | Longest Common Prefix |
|---|---|---|
| "jump" | ["run","run","jump","run"] | "run" → 3 |
| "run" | ["jump","run","jump","run"] | "jump" → 4 |
| "run" | ["jump","run","jump","run"] | "jump" → 4 |
| "jump" | ["jump","run","run","run"] | "run" → 3 |
| "run" | ["jump","run","run","jump"] | "jump" → 4 |
Example 2: words = ["dog","racer","car"], k = 2
Removing any word leaves only pairs with no common prefix → all zeros.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(N * L) | Each word inserted into Trie once. For each removal, traverse Trie path (O(L)) and DFS over Trie nodes (at most O(N*L)) |
| Space | O(N * L) | Trie stores all characters from all strings |
Trie-based simulation avoids combinatorial explosion.
Test Cases
# Basic examples
assert Solution().longestCommonPrefix(["jump","run