Longest Common Prefix of K Strings After Removal solution and explanation
3 more videos on this problem
Longest Common Prefix of K Strings After Removal (Leetcode Biweekly 152) | Earphones RecommendedSoumya Bhattacharjee · 13:49 · 335 views
Leetcode 3485 | Longest Common Prefix of K Strings After Removal | Biweekly Contest 152Road To FAANG · 11:19 · 310 views
3485. Longest Common Prefix of K Strings After Removal (Leetcode Hard)Programming Live with Larry · 31:13 · 280 views
[Go][ENG][Leetcode 3485] Longest Common Prefix of K Strings After RemovalLuiz Felipe · 27:59 · 115 views
The 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 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"):wordsbecomes:["run", "run", "jump", "run"]."run"occurs 3 times. Choosing any two gives the longest common prefix"run"(length 3).
- Removing index 1 (
"run"):wordsbecomes:["jump", "run", "jump", "run"]."jump"occurs twice. Choosing these two gives the longest common prefix"jump"(length 4).
- Removing index 2 (
"run"):wordsbecomes:["jump", "run", "jump", "run"]."jump"occurs twice. Choosing these two gives the longest common prefix"jump"(length 4).
- Removing index 3 (
"jump"):wordsbecomes:["jump", "run", "run", "run"]."run"occurs 3 times. Choosing any two gives the longest common prefix"run"(length 3).
- Removing index 4 ("run"):
wordsbecomes:["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 <= 1051 <= words[i].length <= 104words[i]consists of lowercase English letters.- The sum of
words[i].lengthis smaller than or equal105.
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
class Solution {
static class TrieNode {
int count = 0;
int depth = 0;
int[] children = new int[26];
TrieNode() {
for (int i = 0; i < 26; ++i) children[i] = -1;
}
}
static class SegmentTree {
int n;
int[] tree;
int[] globalCount;
SegmentTree(int n, int[] globalCount) {
this.n = n;
this.globalCount = globalCount;
this.tree = new int[4 * (n + 1)];
for (int i = 0; i < tree.length; i++) tree[i] = -1;
build(1, 1, n);
}
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = globalCount[l] > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
}
void update(int idx, int l, int r, int pos, int newVal) {
if (l == r) {
tree[idx] = newVal > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
update(idx * 2, l, mid, pos, newVal);
} else {
update(idx * 2 + 1, mid + 1, r, pos, newVal);
}
tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query() {
return tree[1];
}
}
public int[] longestCommonPrefix(String[] words, int k) {
int n = words.length;
int[] ans = new int[n];
if (n - 1 < k) return ans;
ArrayList<TrieNode> trie = new ArrayList<>();
trie.add(new TrieNode());
for (String word : words) {
int cur = 0;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (trie.get(cur).children[idx] == -1) {
trie.get(cur).children[idx] = trie.size();
TrieNode node = new TrieNode();
node.depth = trie.get(cur).depth + 1;
trie.add(node);
}
cur = trie.get(cur).children[idx];
trie.get(cur).count++;
}
}
int maxDepth = 0;
for (int i = 1; i < trie.size(); ++i) {
if (trie.get(i).count >= k) {
maxDepth = Math.max(maxDepth, trie.get(i).depth);
}
}
int[] globalCount = new int[maxDepth + 1];
for (int i = 1; i < trie.size(); ++i) {
TrieNode node = trie.get(i);
if (node.count >= k && node.depth <= maxDepth) {
globalCount[node.depth]++;
}
}
List<List<Integer>> fragileList = new ArrayList<>();
for (int i = 0; i < n; ++i) {
fragileList.add(new ArrayList<>());
}
for (int i = 0; i < n; ++i) {
int cur = 0;
for (char c : words[i].toCharArray()) {
int idx = c - 'a';
cur = trie.get(cur).children[idx];
if (trie.get(cur).count == k) {
fragileList.get(i).add(trie.get(cur).depth);
}
}
}
int segSize = maxDepth;
if (segSize >= 1) {
SegmentTree segTree = new SegmentTree(segSize, globalCount);
for (int i = 0; i < n; ++i) {
if (n - 1 < k) {
ans[i] = 0;
} else {
for (int d : fragileList.get(i)) {
segTree.update(1, 1, segSize, d, globalCount[d] - 1);
}
int res = segTree.query();
ans[i] = res == -1 ? 0 : res;
for (int d : fragileList.get(i)) {
segTree.update(1, 1, segSize, d, globalCount[d]);
}
}
}
}
return ans;
}
}class Solution {
public:
struct TrieNode {
int count = 0;
int depth = 0;
int children[26] = {0};
};
class SegmentTree {
public:
int n;
vector<int> tree;
vector<int>& globalCount;
SegmentTree(int n, vector<int>& globalCount)
: n(n)
, globalCount(globalCount) {
tree.assign(4 * (n + 1), -1);
build(1, 1, n);
}
void build(int idx, int l, int r) {
if (l == r) {
tree[idx] = globalCount[l] > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
void update(int idx, int l, int r, int pos, int newVal) {
if (l == r) {
tree[idx] = newVal > 0 ? l : -1;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(idx * 2, l, mid, pos, newVal);
else
update(idx * 2 + 1, mid + 1, r, pos, newVal);
tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
}
int query() {
return tree[1];
}
};
vector<int> longestCommonPrefix(vector<string>& words, int k) {
int n = words.size();
vector<int> ans(n, 0);
if (n - 1 < k) return ans;
vector<TrieNode> trie(1);
for (const string& word : words) {
int cur = 0;
for (char c : word) {
int idx = c - 'a';
if (trie[cur].children[idx] == 0) {
trie[cur].children[idx] = trie.size();
trie.push_back({0, trie[cur].depth + 1});
}
cur = trie[cur].children[idx];
trie[cur].count++;
}
}
int maxDepth = 0;
for (int i = 1; i < trie.size(); ++i) {
if (trie[i].count >= k) {
maxDepth = max(maxDepth, trie[i].depth);
}
}
vector<int> globalCount(maxDepth + 1, 0);
for (int i = 1; i < trie.size(); ++i) {
if (trie[i].count >= k && trie[i].depth <= maxDepth) {
globalCount[trie[i].depth]++;
}
}
vector<vector<int>> fragileList(n);
for (int i = 0; i < n; ++i) {
int cur = 0;
for (char c : words[i]) {
int idx = c - 'a';
cur = trie[cur].children[idx];
if (trie[cur].count == k) {
fragileList[i].push_back(trie[cur].depth);
}
}
}
int segSize = maxDepth;
if (segSize >= 1) {
SegmentTree segTree(segSize, globalCount);
for (int i = 0; i < n; ++i) {
if (n - 1 < k) {
ans[i] = 0;
} else {
for (int d : fragileList[i]) {
segTree.update(1, 1, segSize, d, globalCount[d] - 1);
}
int res = segTree.query();
ans[i] = res == -1 ? 0 : res;
for (int d : fragileList[i]) {
segTree.update(1, 1, segSize, d, globalCount[d]);
}
}
}
}
return ans;
}
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Rebuild Trie for Each Removal | O(n * totalChars) | O(totalChars) | Useful for understanding the prefix-count idea or when constraints are very small |
| Trie with Prefix Frequency + Depth Tracking | O(totalChars log L) | O(totalChars) | Optimal general solution when many removals must be simulated efficiently |
| Trie + Segment Tree / Ordered Set for Valid Depths | O(totalChars log L) | O(totalChars) | Best when quickly querying the maximum prefix depth after updates |
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.