Longest Common Prefix of K Strings After Removal

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.

• 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.

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].

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);
            }
        }
    }
}