Longest Common Prefix of K Strings After Removal

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

1class Solution {2    class TrieNode {3        TrieNode[] children = new TrieNode[26];4        int count = 0;5        int maxLen1 = 0; // Max depth in subtree with count >= k6        int maxLen2 = 0; // Max depth in subtree with count >= k+17    }8 9    public int[] longestCommonPrefix(String[] words, int k) {10        int n = words.length;11        int[] answer = new int[n];12        if (k > n - 1) {13            return answer; // All answers are 014        }15 16        TrieNode root = new TrieNode();17        for (String word : words) {18            TrieNode curr = root;19            for (char c : word.toCharArray()) {20                if (curr.children[c - 'a'] == null) {21                    curr.children[c - 'a'] = new TrieNode();22                }23                curr = curr.children[c - 'a'];24                curr.count++;25            }26        }27 28        dfs(root, 0, k);29 30        for (int i = 0; i < n; i++) {31            String word = words[i];32            TrieNode curr = root;33            int maxLcp = 0;34 35            for (int j = 0; j < word.length(); j++) {36                char c = word.charAt(j);37                TrieNode nextNode = curr.children[c - 'a'];38                39                // Check other branches40                for (int childIdx = 0; childIdx < 26; childIdx++) {41                    TrieNode child = curr.children[childIdx];42                    if (child != null && child != nextNode) {43                        maxLcp = Math.max(maxLcp, child.maxLen1);44                    }45                }46                47                curr = nextNode;48                if (curr.count >= k + 1) {49                    maxLcp = Math.max(maxLcp, j + 1);50                }51            }52            53            // Check branches from the last node of the word's path54            for(TrieNode child : curr.children){55                if(child != null){56                    maxLcp = Math.max(maxLcp, child.maxLen1);57                }58            }59 60            answer[i] = maxLcp;61        }62 63        return answer;64    }65 66    private void dfs(TrieNode node, int depth, int k) {67        if (node == null) return;68 69        node.maxLen1 = (node.count >= k) ? depth : 0;70        node.maxLen2 = (node.count >= k + 1) ? depth : 0;71 72        for (TrieNode child : node.children) {73            if (child != null) {74                dfs(child, depth + 1, k);75                node.maxLen1 = Math.max(node.maxLen1, child.maxLen1);76                node.maxLen2 = Math.max(node.maxLen2, child.maxLen2);77            }78        }79    }80}

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

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    class TrieNode {6        TrieNode[] children = new TrieNode[26];7        int count = 0;8    }9 10    public int[] longestCommonPrefix(String[] words, int k) {11        int n = words.length;12        int[] answer = new int[n];13 14        for (int i = 0; i < n; i++) {15            if (n - 1 < k) {16                answer[i] = 0;17                continue;18            }19 20            List<String> remainingWords = new ArrayList<>();21            for (int j = 0; j < n; j++) {22                if (i == j) continue;23                remainingWords.add(words[j]);24            }25 26            TrieNode root = new TrieNode();27            for (String word : remainingWords) {28                TrieNode curr = root;29                for (char c : word.toCharArray()) {30                    if (curr.children[c - 'a'] == null) {31                        curr.children[c - 'a'] = new TrieNode();32                    }33                    curr = curr.children[c - 'a'];34                    curr.count++;35                }36            }37 38            answer[i] = findMaxLCP(root, k, 0);39        }40        return answer;41    }42 43    private int findMaxLCP(TrieNode node, int k, int depth) {44        if (node == null) {45            return 0;46        }47 48        int maxLen = 0;49        if (node.count >= k) {50            maxLen = depth;51        }52 53        for (TrieNode child : node.children) {54            if (child != null) {55                maxLen = Math.max(maxLen, findMaxLCP(child, k, depth + 1));56            }57        }58        return maxLen;59    }60}