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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3
4

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 <= 10^5
  • 1 <= words[i].length <= 10^4
  • words[i] consists of lowercase English letters.
  • The sum of words[i].length is smaller than or equal 105.

Examples

Solution

Method 1 – Trie with Prefix/Suffix Counting (1)

Intuition

To efficiently find the longest common prefix among any k strings after removing one, we can use a trie to count the number of strings sharing each prefix. By precomputing prefix and suffix tries, we can answer each query in O(L) time, where L is the string length.

Approach

  1. Build a trie for all words except the one being removed, and for each node, store the count of words passing through it.
  2. For each removal, merge the prefix trie (for words before the removed index) and the suffix trie (for words after the removed index).
  3. For each position, traverse the merged trie and find the deepest node with count >= k.
  4. The length of the deepest such node is the answer for that removal.

Code

1

// Omitted for brevity due to complexity and space. See Python for main logic.

1

// Omitted for brevity due to complexity and space. See Python for main logic.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

class Solution:
    def longestCommonPrefixAfterRemoval(self, words: list[str], k: int) -> list[int]:
        n = len(words)
        pre = [TrieNode() for _ in range(n+1)]
        suf = [TrieNode() for _ in range(n+1)]
        def insert(root, word):
            node = root
            for c in word:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
                node.count += 1
        # Build prefix tries
        for i in range(n):
            pre[i+1] = pre[i]
            insert(pre[i+1], words[i])
        # Build suffix tries
        for i in range(n-1, -1, -1):
            suf[i] = suf[i+1]
            insert(suf[i], words[i])
        ans = [0] * n
        for i in range(n):
            node = pre[i]
            node2 = suf[i+1]
            l = 0
            while True:
                found = False
                for c in node.children:
                    if c in node2.children:
                        cnt = node.children[c].count + node2.children[c].count
                        if cnt >= k:
                            node = node.children[c]
                            node2 = node2.children[c]
                            l += 1
                            found = True
                            break
                if not found:
                    break
            ans[i] = l
        return ans

Complexity

  • ⏰ Time complexity: O(nL), where n is the number of words and L is the average word length, for building tries and answering queries.
  • 🧺 Space complexity: O(nL), for storing the tries.