Longest Common Prefix of K Strings After Removal - Solution & Explanation

Problem Overview: You are given an array of strings and an integer k. For every index i, remove words[i] and determine the maximum length of a prefix shared by at least k of the remaining strings. The task is to return this value for every removal.

Approach 1: Rebuild LCP for Each Removal (Brute Force) (Time: O(n * totalChars), Space: O(totalChars))

For each index i, remove the string and recompute the longest prefix shared by any k remaining strings. A straightforward way is to rebuild a Trie from the remaining words and track how many strings pass through each node. While inserting, maintain counts and record the deepest node whose frequency is at least k. This works because Trie levels directly correspond to prefix length. However, rebuilding the structure for every removal repeats the same work and becomes too slow when the number of strings or total characters is large.

Approach 2: Trie with Prefix Frequency Tracking (Optimized) (Time: O(totalChars log L), Space: O(totalChars))

Insert all words once into a Trie. Each node stores how many strings share that prefix. For every depth, track how many Trie nodes have frequency ≥ k. The longest valid prefix is simply the maximum depth with at least one such node. When simulating the removal of words[i], walk through its Trie path and temporarily decrement the frequency of those nodes. If a node’s count drops from k to k-1, that depth may lose a valid prefix. Maintain the set of valid depths using a structure like a segment tree or ordered set so you can quickly query the maximum depth that still satisfies the condition. After computing the answer, restore the counts before processing the next removal.

The key insight is that only prefixes along the removed word’s path can change validity. All other Trie nodes remain unaffected, which keeps updates localized and efficient. This transforms repeated full recomputation into small incremental updates.

Recommended for interviews: The Trie-based counting approach is the expected solution. It demonstrates understanding of prefix structures, frequency tracking, and efficient updates after simulated deletions. A brute force Trie rebuild shows the correct intuition about prefixes, but optimizing it with prefix counts and depth tracking highlights stronger algorithmic design using arrays, strings, and Trie structures.