# Longest Common Prefix of K Strings After Removal
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-common-prefix-of-k-strings-after-removal)
Canonical: https://scaleengineer.com/dsa/problems/longest-common-prefix-of-k-strings-after-removal
**Data structures:** Array, String, Trie
---
## 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"`):  
  * `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`.

# Approaches
## Brute Force by Rebuilding Trie
This approach iterates through each word in the input array. For each word, it simulates its removal by creating a temporary list of the remaining words. Then, it builds a Trie data structure from this temporary list. By traversing the constructed Trie, it finds the longest prefix shared by at least `k` strings.
**Time:** O(N * S), where `N` is the number of words and `S` is the total length of all characters in `words`. For each of the `N` words, we iterate through the rest of the words to build a Trie, which takes `O(S)` time. This process is repeated `N` times. · **Space:** O(S), where `S` is the total number of characters in all words. This space is required to store the Trie for the `N-1` words in each iteration. The Trie size is proportional to `S`.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Extremely inefficient due to redundant computations.; The time complexity of `O(N * S)` makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error on large test cases.
### Explanation
The main idea is to solve the problem for each index `i` independently. We loop from `i = 0` to `n-1`, where `n` is the number of words. Inside the loop, we first check if removing `words[i]` leaves fewer than `k` strings. If `n-1 < k`, the answer for this index is 0.

Otherwise, we construct a new list of strings containing all words from the original array except `words[i]`. With this new list of `n-1` strings, we build a Trie. A Trie is a tree-like data structure perfect for handling prefix-related problems. Each node in the Trie represents a character, and a path from the root to a node represents a prefix.

While building the Trie, we store a `count` at each node, which signifies how many words in the current list share the prefix represented by that node. After the Trie is built, we perform a traversal (like Depth First Search) starting from the root. During the traversal, we check each node's `count`. If `count >= k`, it means the prefix corresponding to this node is shared by at least `k` strings. We are interested in the longest such prefix, so we keep track of the maximum depth of any node that satisfies this condition. The depth of a node is equivalent to the length of the prefix it represents. This maximum depth is the answer for index `i`. We repeat this entire process for all indices `i`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int count = 0;
    }

    public int[] longestCommonPrefix(String[] words, int k) {
        int n = words.length;
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            if (n - 1 < k) {
                answer[i] = 0;
                continue;
            }

            List<String> remainingWords = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                remainingWords.add(words[j]);
            }

            TrieNode root = new TrieNode();
            for (String word : remainingWords) {
                TrieNode curr = root;
                for (char c : word.toCharArray()) {
                    if (curr.children[c - 'a'] == null) {
                        curr.children[c - 'a'] = new TrieNode();
                    }
                    curr = curr.children[c - 'a'];
                    curr.count++;
                }
            }

            answer[i] = findMaxLCP(root, k, 0);
        }
        return answer;
    }

    private int findMaxLCP(TrieNode node, int k, int depth) {
        if (node == null) {
            return 0;
        }

        int maxLen = 0;
        if (node.count >= k) {
            maxLen = depth;
        }

        for (TrieNode child : node.children) {
            if (child != null) {
                maxLen = Math.max(maxLen, findMaxLCP(child, k, depth + 1));
            }
        }
        return maxLen;
    }
}
```
### Algorithm
- Initialize an answer array `ans` of the same size as `words`.
- For each index `i` from `0` to `words.length - 1`:
  - If `words.length - 1 < k`, set `ans[i] = 0` and continue to the next index.
  - Create a temporary list `tempWords` containing all strings from `words` except `words[i]`.
  - Build a new Trie from `tempWords`. A Trie node will contain an array of children and a `count` field.
  - For each string added to the Trie, increment the `count` of each node along its path.
  - Initialize a variable `maxLength = 0`.
  - Traverse the newly built Trie using a Depth First Search (DFS). For each node visited at depth `d`:
    - If the node's `count` is greater than or equal to `k`, it means the prefix is common to at least `k` strings. Update `maxLength = max(maxLength, d)`.
  - After the traversal, `maxLength` holds the length of the longest common prefix for the current subproblem. Set `ans[i] = maxLength`.
- After the loop finishes, return the `ans` array.

## Optimized Trie with Pre-computation
This efficient approach avoids rebuilding the Trie for each word. Instead, it builds a single Trie for all words and pre-computes necessary information. For each word to be removed, it uses this pre-computed data to quickly find the longest common prefix among the remaining strings.
**Time:** O(S * A), where `S` is the total length of all words and `A` is the alphabet size. Building the Trie and the DFS for pre-computation takes `O(S)`. Calculating each answer takes `O(length(word) * A)`. The total for all words sums up to `O(S * A)`. · **Space:** O(S * A), where `S` is the total length of all words and `A` is the alphabet size (26). This space is for storing the Trie. Each of the `O(S)` nodes has an array of `A` children pointers and a few integer fields.
**Pros:** Highly efficient and passes the given constraints.; Avoids redundant computations by using a single Trie and pre-computation.; Scales well with a large number of words.
**Cons:** More complex to implement and reason about compared to the brute-force approach.; Requires more space to store the pre-computed values in each Trie node.
### Explanation
The core idea is to build one Trie for all `n` words and then, for each `i`, calculate the result without modifying the Trie structure. First, we insert all words into a single Trie where each node stores a `count` of how many words pass through it.

The key insight is that when we remove `words[i]`, the `count` of nodes corresponding to prefixes of `words[i]` decreases by 1, while counts for all other nodes remain the same. A prefix `P` is a candidate for the LCP if its count among the remaining `n-1` strings is at least `k`.
- If `P` is a prefix of `words[i]`, its new count is `original_count - 1`. It's a candidate if `original_count - 1 >= k`, i.e., `original_count >= k+1`.
- If `P` is not a prefix of `words[i]`, its count is unchanged. It's a candidate if `original_count >= k`.

To find the maximum length efficiently, we pre-compute two values for each node `u` in the Trie using a post-order DFS traversal:
1.  `maxLen1`: The maximum length of a prefix in the subtree of `u` (inclusive) whose original count is `>= k`.
2.  `maxLen2`: The maximum length of a prefix in the subtree of `u` (inclusive) whose original count is `>= k+1`.

After this pre-computation, we iterate through each `words[i]` to calculate `answer[i]`. We traverse the path of `words[i]` in the Trie. At each node `p` on the path, the maximum LCP length can come from two sources:
1.  Prefixes of `words[i]` itself. We check if `count(p) >= k+1`.
2.  Prefixes not belonging to `words[i]`. These are found in the subtrees of `p`'s children that are *not* on the path of `words[i]`. For any such "off-path" child `c`, the maximum length we can get from its subtree is `maxLen1[c]`, since counts in that subtree are unaffected.

We take the maximum of all these possibilities to find `answer[i]`.

```java
class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int count = 0;
        int maxLen1 = 0; // Max depth in subtree with count >= k
        int maxLen2 = 0; // Max depth in subtree with count >= k+1
    }

    public int[] longestCommonPrefix(String[] words, int k) {
        int n = words.length;
        int[] answer = new int[n];
        if (k > n - 1) {
            return answer; // All answers are 0
        }

        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                if (curr.children[c - 'a'] == null) {
                    curr.children[c - 'a'] = new TrieNode();
                }
                curr = curr.children[c - 'a'];
                curr.count++;
            }
        }

        dfs(root, 0, k);

        for (int i = 0; i < n; i++) {
            String word = words[i];
            TrieNode curr = root;
            int maxLcp = 0;

            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                TrieNode nextNode = curr.children[c - 'a'];
                
                // Check other branches
                for (int childIdx = 0; childIdx < 26; childIdx++) {
                    TrieNode child = curr.children[childIdx];
                    if (child != null && child != nextNode) {
                        maxLcp = Math.max(maxLcp, child.maxLen1);
                    }
                }
                
                curr = nextNode;
                if (curr.count >= k + 1) {
                    maxLcp = Math.max(maxLcp, j + 1);
                }
            }
            
            // Check branches from the last node of the word's path
            for(TrieNode child : curr.children){
                if(child != null){
                    maxLcp = Math.max(maxLcp, child.maxLen1);
                }
            }

            answer[i] = maxLcp;
        }

        return answer;
    }

    private void dfs(TrieNode node, int depth, int k) {
        if (node == null) return;

        node.maxLen1 = (node.count >= k) ? depth : 0;
        node.maxLen2 = (node.count >= k + 1) ? depth : 0;

        for (TrieNode child : node.children) {
            if (child != null) {
                dfs(child, depth + 1, k);
                node.maxLen1 = Math.max(node.maxLen1, child.maxLen1);
                node.maxLen2 = Math.max(node.maxLen2, child.maxLen2);
            }
        }
    }
}
```
### Algorithm
- Build a single Trie for all words in the input array. Each node should store a `count` of words passing through it.
- Perform a post-order DFS traversal on the Trie to compute two values for each node `u` at depth `d`:
  - `maxLen1[u]`: The maximum length of a prefix in the subtree of `u` (inclusive) whose original count is `>= k`.
  - `maxLen2[u]`: The maximum length of a prefix in the subtree of `u` (inclusive) whose original count is `>= k+1`.
- Initialize an answer array `ans` of the same size as `words`.
- For each index `i` from `0` to `words.length - 1`:
  - If `words.length - 1 < k`, set `ans[i] = 0` and continue.
  - Initialize `currentMax = 0`.
  - Traverse the path for `words[i]` in the Trie, starting from the root. Let the current node be `p`.
  - At each step of the traversal for `words[i]` (for character at depth `d`):
    - Let the next node on the path be `childOnPath`.
    - Iterate through all children `c` of the current node `p`. If a child `c` is not `childOnPath`, it represents a branch of prefixes not found in `words[i]`. Update `currentMax = max(currentMax, c.maxLen1)`.
    - Move to the next node: `p = childOnPath`.
    - The prefix ending at the new node `p` is a prefix of `words[i]`. Its count will be reduced by 1. It is a valid LCP if its original count was `>= k+1`. If so, update `currentMax = max(currentMax, d + 1)`.
  - After the traversal for `words[i]` is complete, the final node `p` might have children. These branches are also not part of `words[i]`. For all children `c` of `p`, update `currentMax = max(currentMax, c.maxLen1)`.
  - Set `ans[i] = currentMax`.
- Return `ans`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```