Skip to main content
Talentd

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

HardArrayStringTrie7 min read
Practice this problem

Problem Statement

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 ith element.

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

 

Example 1:

Input: words = ["jump","run","run","jump","run"], k = 2

Output: [3,4,4,3,4]

Explanation:

  • Removing index 0 ("jump"):
    • words becomes: ["run", "run", "jump", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
  • Removing index 1 ("run"):
    • words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
  • Removing index 2 ("run"):
    • words becomes: ["jump", "run", "jump", "run"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).
  • Removing index 3 ("jump"):
    • words becomes: ["jump", "run", "run", "run"]. "run" occurs 3 times. Choosing any two gives the longest common prefix "run" (length 3).
  • Removing index 4 ("run"):
    • words becomes: ["jump", "run", "run", "jump"]. "jump" occurs twice. Choosing these two gives the longest common prefix "jump" (length 4).

Example 2:

Input: words = ["dog","racer","car"], k = 2

Output: [0,0,0]

Explanation:

  • Removing any index results in an answer of 0.

 

Constraints:

  • 1 <= k <= words.length <= 105
  • 1 <= words[i].length <= 104
  • words[i] consists of lowercase English letters.
  • The sum of words[i].length is smaller than or equal 105.

Approach Overview

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.

Solution

Code

JavaC++

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Rebuild Trie for Each RemovalO(n * totalChars)O(totalChars)Useful for understanding the prefix-count idea or when constraints are very small
Trie with Prefix Frequency + Depth TrackingO(totalChars log L)O(totalChars)Optimal general solution when many removals must be simulated efficiently
Trie + Segment Tree / Ordered Set for Valid DepthsO(totalChars log L)O(totalChars)Best when quickly querying the maximum prefix depth after updates

Video Solution

Longest Common Prefix of K Strings After Removal (Leetcode Biweekly 152) | Earphones Recommended • Soumya Bhattacharjee • 335 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Longest Common Prefix of K Strings After Removal easy or hard?
The problem is rated Hard because it combines multiple concepts: Trie construction, prefix frequency tracking, and efficient updates after removing strings. A naive solution is straightforward, but designing an optimized approach that avoids rebuilding the Trie for every removal requires deeper algorithmic insight.
Longest Common Prefix of K Strings After Removal Python/Java solution
Most implementations build a Trie where each node tracks the number of strings sharing that prefix. While processing each removal, counts along the removed word's path are temporarily decreased and the deepest valid prefix length is queried. The same logic works across Python, Java, C++, and Go with similar complexity.
What is the best approach for Longest Common Prefix of K Strings After Removal?
The most efficient approach builds a Trie for all strings and stores how many words share each prefix. While simulating the removal of a word, only the nodes along its path need updates. Tracking depths where prefix frequency is at least k allows quick retrieval of the longest valid prefix. This reduces repeated recomputation and keeps the complexity around O(total characters log L).
Is Longest Common Prefix of K Strings After Removal asked at Google/Amazon/Meta?
Problems involving Trie prefix counting and dynamic string updates frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of longest common prefix problems and prefix frequency queries are common because they test knowledge of Trie structures and efficient updates.
What data structure is used in Longest Common Prefix of K Strings After Removal?
The core data structure is a Trie (prefix tree) that stores every prefix of the input strings along with a frequency count. Additional structures such as arrays, segment trees, or ordered sets are used to quickly track which prefix lengths remain valid after simulated removals.
What is the time complexity of Longest Common Prefix of K Strings After Removal?
The optimized Trie-based solution runs in O(totalCharacters log L), where L is the maximum string length. Building the Trie takes O(totalCharacters), and each simulated removal updates only the nodes along that word's prefix path. Querying the deepest valid prefix is handled with a structure like a segment tree or ordered set.
How to solve Longest Common Prefix of K Strings After Removal in O(total characters log L)?
Insert all strings into a Trie and store the frequency of each prefix node. Maintain a structure that records which prefix depths have at least k strings passing through. When removing a word, decrement counts along its path and update the affected depths. Query the maximum depth that still has frequency ≥ k, then restore the counts before processing the next word.

Ready to solve this problem?

Practice Longest Common Prefix of K Strings After Removal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays