3485. Longest Common Prefix of K Strings After Removal

Problem Description

You have an array of strings called words and an integer k. Your task is to find, for each string in the array, what happens when you remove that string and then look for the longest common prefix among any k strings from the remaining strings.

More specifically:

For each index i from 0 to words.length - 1, you need to:
1. Temporarily remove the string at index i from the array
2. From the remaining strings, select any k strings (they must be at different indices)
3. Find the longest common prefix among those k selected strings
4. Among all possible selections of k strings, find the maximum length of the common prefix

The result should be an array answer where answer[i] represents the maximum length of the longest common prefix when the i-th string is removed.

Special case: If removing the i-th string leaves you with fewer than k strings in the array, then answer[i] should be 0.

For example, if you have words = ["abc", "abd", "abcd", "xy"] and k = 2:

When removing index 0 ("abc"), you can select "abd" and "abcd" which share prefix "ab" of length 2
When removing index 1 ("abd"), you can select "abc" and "abcd" which share prefix "abc" of length 3
And so on for each index

The solution uses a Trie data structure to efficiently store all strings and track how many strings pass through each node. It also uses a Segment Tree to quickly query the maximum depth at which at least k strings share a common prefix, while temporarily adjusting counts when a string is "removed" from consideration.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that finding the longest common prefix among k strings is fundamentally about finding the deepest point in a prefix tree (Trie) where at least k strings pass through.

When we build a Trie with all the strings, each node represents a prefix, and we can count how many strings pass through each node. A node with count ≥ k means that at least k strings share that prefix. The deeper such a node is in the Trie, the longer the common prefix.

Now, when we "remove" the i-th string, we're essentially asking: what's the longest prefix shared by at least k strings when this particular string is not counted? This changes the counts at certain nodes in the Trie.

The challenge is that we need to do this efficiently for each string. We can't rebuild the Trie each time. Instead, we observe that:

When we remove a string, only the nodes along its path in the Trie are affected (their counts decrease by 1)
A node becomes "fragile" when its count is exactly k - removing one string that passes through it would make it invalid (count becomes k-1)

For efficient querying of the maximum valid depth after temporary removals, we use a Segment Tree. The Segment Tree tracks, for each depth level, how many nodes at that depth have count ≥ k. When we temporarily remove a string:

We decrease the count for depths where the string passes through fragile nodes (count = k)
Query the maximum depth that still has at least one valid node
Restore the counts back

This approach avoids rebuilding the Trie for each removal and uses the Segment Tree's O(log n) update and query operations to efficiently find the answer for each string.

Learn more about Trie patterns.

Solution Approach

The solution uses a combination of Trie and Segment Tree data structures to efficiently solve the problem.

Step 1: Build the Trie

First, we construct a Trie to store all strings and track prefix information:

ArrayList<TrieNode> [trie](/problems/trie_intro) = new ArrayList<>();
trie.add(new TrieNode());

for (String word : words) {
    int cur = 0;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if ([trie](/problems/trie_intro).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++;
    }
}

Each TrieNode stores:

count: number of strings passing through this node
depth: the depth in the Trie (represents prefix length)
children: array of child node indices

Step 2: Find Maximum Valid Depth and Count Valid Nodes

We determine the maximum depth where at least k strings share a prefix and count how many nodes at each depth are valid:

int maxDepth = 0;
for (int i = 1; i < [trie](/problems/trie_intro).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](/problems/trie_intro).size(); ++i) {
    TrieNode node = trie.get(i);
    if (node.count >= k && node.depth <= maxDepth) {
        globalCount[node.depth]++;
    }
}

Step 3: Identify Fragile Nodes

For each string, we find the "fragile" nodes - nodes with exactly k count that this string passes through:

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](/problems/trie_intro).get(cur).children[idx];
        if (trie.get(cur).count == k) {
            fragileList.get(i).add(trie.get(cur).depth);
        }
    }
}

Step 4: Use Segment Tree for Efficient Queries

The Segment Tree maintains the maximum depth that has at least one valid node. For each string removal:

SegmentTree segTree = new SegmentTree(segSize, globalCount);
for (int i = 0; i < n; ++i) {
    // Temporarily decrease counts at fragile depths
    for (int d : fragileList.get(i)) {
        segTree.update(1, 1, segSize, d, globalCount[d] - 1);
    }
  
    // Query maximum valid depth
    int res = segTree.query();
    ans[i] = res == -1 ? 0 : res;
  
    // Restore counts
    for (int d : fragileList.get(i)) {
        segTree.update(1, 1, segSize, d, globalCount[d]);
    }
}

The Segment Tree's key operations:

build(): Initializes the tree with global counts
update(): Updates the count at a specific depth
query(): Returns the maximum depth with at least one valid node

The tree maintains that tree[idx] stores the maximum valid depth in its range, where a depth is valid if it has at least one node with count ≥ k.

Time Complexity

Building Trie: O(N × L) where N is number of words and L is average length
Building Segment Tree: O(maxDepth)
Processing each word: O(L × log(maxDepth))
Overall: O(N × L × log(maxDepth))

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with words = ["abc", "ab", "abd", "abcd"] and k = 2.

Step 1: Build the Trie

We insert all words into the Trie, tracking count at each node:

        root (count=0)
          |
         'a' (count=4, depth=1)
          |
         'b' (count=4, depth=2)
        /   \
      'c'    'd' (count=2, depth=3)
   (count=2)  |
      |      'c'
     'd'   (count=1, depth=4)
  (count=1)

Step 2: Find Valid Nodes and Maximum Depth

Since k = 2, we need nodes with count ≥ 2:

Depth 1: node 'a' has count=4 ≥ 2 ✓
Depth 2: node 'b' has count=4 ≥ 2 ✓
Depth 3: node 'c' has count=2 ≥ 2 ✓, node 'd' has count=2 ≥ 2 ✓

Maximum valid depth = 3

Global count array: [0, 1, 1, 2] (representing counts at depths 0, 1, 2, 3)

Step 3: Identify Fragile Nodes for Each Word

A node is "fragile" if it has exactly count = k = 2.

Word "abc": passes through 'a'(4) → 'b'(4) → 'c'(2)
- Fragile nodes: 'c' at depth 3
- fragileList[0] = [3]
Word "ab": passes through 'a'(4) → 'b'(4)
- Fragile nodes: none
- fragileList[1] = []
Word "abd": passes through 'a'(4) → 'b'(4) → 'd'(2)
- Fragile nodes: 'd' at depth 3
- fragileList[2] = [3]
Word "abcd": passes through 'a'(4) → 'b'(4) → 'c'(2) → 'd'(1)
- Fragile nodes: 'c' at depth 3
- fragileList[3] = [3]

Step 4: Process Each Word Removal with Segment Tree

Initial Segment Tree with globalCount = [0, 1, 1, 2]:

For i=0 (remove "abc"):

Update depth 3: globalCount[3] - 1 = 2 - 1 = 1
Query: Maximum depth with count > 0 is still 3
answer[0] = 3 (words "ab", "abd", "abcd" can form pairs with prefix "ab" of length 2, or "abd" and "abcd" with prefix "ab" of length 2)
Restore depth 3 back to 2

For i=1 (remove "ab"):

No fragile nodes to update
Query: Maximum depth with count > 0 is 3
answer[1] = 3 (words "abc", "abd", "abcd" - selecting "abd" and "abcd" gives prefix "abd" of length 3)

For i=2 (remove "abd"):

Update depth 3: globalCount[3] - 1 = 2 - 1 = 1
Query: Maximum depth with count > 0 is still 3
answer[2] = 3 (words "abc", "ab", "abcd" - selecting "abc" and "abcd" gives prefix "abc" of length 3)
Restore depth 3 back to 2

For i=3 (remove "abcd"):

Update depth 3: globalCount[3] - 1 = 2 - 1 = 1
Query: Maximum depth with count > 0 is still 3
answer[3] = 3 (words "abc", "ab", "abd" - selecting "abc" and "abd" gives prefix "ab" of length 2, but we can also select "abc" and "ab" or "ab" and "abd" with prefix "ab" of length 2)

Wait, let me recalculate answer[3] more carefully:

After removing "abcd", we have ["abc", "ab", "abd"]
Best k=2 selection: "abc" and "ab" share prefix "ab" (length 2)
Or "ab" and "abd" share prefix "ab" (length 2)
answer[3] = 2

Final answer: [3, 3, 3, 2]

The key insight is that the Segment Tree efficiently tracks which depths remain valid after temporarily removing a string's contribution through its fragile nodes.

Solution Implementation

1class Solution:
2    def longestCommonPrefix(self, words: List[str], k: int) -> List[int]:
3        """
4        Find the longest common prefix for each word when that word is excluded,
5        where the prefix must appear in at least k of the remaining words.
6        """
7        n = len(words)
8        result = [0] * n
9      
10        # Early return if not enough words for k-common prefix
11        if n - 1 < k:
12            return result
13      
14        # Build trie from all words
15        # Each node stores: count (occurrences), depth (prefix length), children (dict of char->node_index)
16        trie = [{'count': 0, 'depth': 0, 'children': {}}]  # Initialize with root node
17      
18        for word in words:
19            current_node = 0
20            for ch in word:
21                # Create new node if path doesn't exist
22                if ch not in trie[current_node]['children']:
23                    trie[current_node]['children'][ch] = len(trie)
24                    trie.append({
25                        'count': 0,
26                        'depth': trie[current_node]['depth'] + 1,
27                        'children': {}
28                    })
29                current_node = trie[current_node]['children'][ch]
30                trie[current_node]['count'] += 1
31      
32        # Find maximum depth among nodes with count >= k
33        max_depth = 0
34        for i in range(1, len(trie)):
35            if trie[i]['count'] >= k:
36                max_depth = max(max_depth, trie[i]['depth'])
37      
38        # Count nodes at each depth that have count >= k
39        global_count = [0] * (max_depth + 1)
40        for i in range(1, len(trie)):
41            if trie[i]['count'] >= k and trie[i]['depth'] <= max_depth:
42                global_count[trie[i]['depth']] += 1
43      
44        # Find fragile depths for each word (nodes with exactly k occurrences)
45        fragile_depths = [[] for _ in range(n)]
46        for i in range(n):
47            current_node = 0
48            for ch in words[i]:
49                current_node = trie[current_node]['children'][ch]
50                if trie[current_node]['count'] == k:
51                    fragile_depths[i].append(trie[current_node]['depth'])
52      
53        # Process each word using segment tree if there are valid depths
54        segment_size = max_depth
55        if segment_size >= 1:
56            segment_tree = SegmentTree(segment_size, global_count)
57          
58            for i in range(n):
59                if n - 1 < k:
60                    result[i] = 0
61                else:
62                    # Temporarily decrease counts for fragile depths
63                    for depth in fragile_depths[i]:
64                        segment_tree.update(1, 1, segment_size, depth, global_count[depth] - 1)
65                  
66                    # Query maximum valid depth
67                    max_valid_depth = segment_tree.query()
68                    result[i] = 0 if max_valid_depth == -1 else max_valid_depth
69                  
70                    # Restore original counts
71                    for depth in fragile_depths[i]:
72                        segment_tree.update(1, 1, segment_size, depth, global_count[depth])
73      
74        return result
75
76
77class SegmentTree:
78    """
79    Segment tree for efficient range maximum queries.
80    Used to find the maximum depth with valid count.
81    """
82  
83    def __init__(self, n: int, global_count: List[int]):
84        """
85        Initialize segment tree with given size and count array.
86      
87        Args:
88            n: Size of the segment tree
89            global_count: Reference to global count array
90        """
91        self.n = n
92        self.global_count = global_count
93        self.tree = [-1] * (4 * (n + 1))
94        self.build(1, 1, n)
95  
96    def build(self, node_idx: int, left: int, right: int):
97        """
98        Build segment tree recursively.
99      
100        Args:
101            node_idx: Current node index in the tree
102            left: Left boundary of the range
103            right: Right boundary of the range
104        """
105        if left == right:
106            # Leaf node: store depth if count > 0, otherwise -1
107            self.tree[node_idx] = left if self.global_count[left] > 0 else -1
108            return
109      
110        mid = (left + right) // 2
111        self.build(node_idx * 2, left, mid)
112        self.build(node_idx * 2 + 1, mid + 1, right)
113        # Internal node stores maximum of children
114        self.tree[node_idx] = max(self.tree[node_idx * 2], self.tree[node_idx * 2 + 1])
115  
116    def update(self, node_idx: int, left: int, right: int, position: int, new_value: int):
117        """
118        Update a single position in the segment tree.
119      
120        Args:
121            node_idx: Current node index in the tree
122            left: Left boundary of the range
123            right: Right boundary of the range
124            position: Position to update
125            new_value: New value for the position
126        """
127        if left == right:
128            # Update leaf node based on new value
129            self.tree[node_idx] = left if new_value > 0 else -1
130            return
131      
132        mid = (left + right) // 2
133        if position <= mid:
134            self.update(node_idx * 2, left, mid, position, new_value)
135        else:
136            self.update(node_idx * 2 + 1, mid + 1, right, position, new_value)
137        # Update internal node with maximum of children
138        self.tree[node_idx] = max(self.tree[node_idx * 2], self.tree[node_idx * 2 + 1])
139  
140    def query(self) -> int:
141        """
142        Query the maximum value in the entire range.
143      
144        Returns:
145            Maximum valid depth or -1 if none exists
146        """
147        return self.tree[1]  # Root contains the maximum
148

1class Solution {
2    /**
3     * TrieNode class represents a node in the Trie data structure
4     */
5    static class TrieNode {
6        int count = 0;          // Number of words passing through this node
7        int depth = 0;          // Depth of this node in the trie (length of prefix)
8        int[] children = new int[26];  // Array to store indices of child nodes (for 26 letters)
9
10        TrieNode() {
11            // Initialize all children as -1 (no child exists)
12            for (int i = 0; i < 26; i++) {
13                children[i] = -1;
14            }
15        }
16    }
17
18    /**
19     * SegmentTree class for efficient range maximum queries
20     */
21    static class SegmentTree {
22        int n;                  // Size of the segment tree
23        int[] tree;             // Array to store segment tree nodes
24        int[] globalCount;      // Array to store global counts for each depth
25
26        SegmentTree(int n, int[] globalCount) {
27            this.n = n;
28            this.globalCount = globalCount;
29            this.tree = new int[4 * (n + 1)];
30          
31            // Initialize tree with -1
32            for (int i = 0; i < tree.length; i++) {
33                tree[i] = -1;
34            }
35          
36            // Build the segment tree
37            build(1, 1, n);
38        }
39
40        /**
41         * Build the segment tree recursively
42         */
43        void build(int nodeIndex, int left, int right) {
44            if (left == right) {
45                // Leaf node: set value based on globalCount
46                tree[nodeIndex] = globalCount[left] > 0 ? left : -1;
47                return;
48            }
49          
50            int mid = (left + right) / 2;
51            // Build left subtree
52            build(nodeIndex * 2, left, mid);
53            // Build right subtree
54            build(nodeIndex * 2 + 1, mid + 1, right);
55            // Merge results from children
56            tree[nodeIndex] = Math.max(tree[nodeIndex * 2], tree[nodeIndex * 2 + 1]);
57        }
58
59        /**
60         * Update a single position in the segment tree
61         */
62        void update(int nodeIndex, int left, int right, int position, int newValue) {
63            if (left == right) {
64                // Update leaf node
65                tree[nodeIndex] = newValue > 0 ? left : -1;
66                return;
67            }
68          
69            int mid = (left + right) / 2;
70            if (position <= mid) {
71                // Update left subtree
72                update(nodeIndex * 2, left, mid, position, newValue);
73            } else {
74                // Update right subtree
75                update(nodeIndex * 2 + 1, mid + 1, right, position, newValue);
76            }
77            // Update current node based on children
78            tree[nodeIndex] = Math.max(tree[nodeIndex * 2], tree[nodeIndex * 2 + 1]);
79        }
80
81        /**
82         * Query the maximum value in the entire range
83         */
84        int query() {
85            return tree[1];  // Root of the segment tree
86        }
87    }
88
89    /**
90     * Find the longest common prefix for each word when excluding it from the word list
91     * @param words Array of words to process
92     * @param k Minimum number of words that must share a common prefix
93     * @return Array where ans[i] is the length of longest common prefix when words[i] is excluded
94     */
95    public int[] longestCommonPrefix(String[] words, int k) {
96        int n = words.length;
97        int[] answer = new int[n];
98      
99        // If total words minus one is less than k, no valid prefix exists
100        if (n - 1 < k) {
101            return answer;
102        }
103
104        // Initialize trie with root node
105        ArrayList<TrieNode> trie = new ArrayList<>();
106        trie.add(new TrieNode());
107
108        // Build the trie with all words
109        for (String word : words) {
110            int currentNodeIndex = 0;
111          
112            for (char character : word.toCharArray()) {
113                int charIndex = character - 'a';
114              
115                // Create new node if path doesn't exist
116                if (trie.get(currentNodeIndex).children[charIndex] == -1) {
117                    trie.get(currentNodeIndex).children[charIndex] = trie.size();
118                    TrieNode newNode = new TrieNode();
119                    newNode.depth = trie.get(currentNodeIndex).depth + 1;
120                    trie.add(newNode);
121                }
122              
123                // Move to child node and increment count
124                currentNodeIndex = trie.get(currentNodeIndex).children[charIndex];
125                trie.get(currentNodeIndex).count++;
126            }
127        }
128
129        // Find maximum depth where at least k words share a prefix
130        int maxDepth = 0;
131        for (int i = 1; i < trie.size(); i++) {
132            if (trie.get(i).count >= k) {
133                maxDepth = Math.max(maxDepth, trie.get(i).depth);
134            }
135        }
136
137        // Count valid prefixes at each depth
138        int[] globalCount = new int[maxDepth + 1];
139        for (int i = 1; i < trie.size(); i++) {
140            TrieNode node = trie.get(i);
141            if (node.count >= k && node.depth <= maxDepth) {
142                globalCount[node.depth]++;
143            }
144        }
145
146        // Build list of fragile depths for each word
147        // A depth is fragile for a word if removing the word would make count < k
148        List<List<Integer>> fragileDepths = new ArrayList<>();
149        for (int i = 0; i < n; i++) {
150            fragileDepths.add(new ArrayList<>());
151        }
152
153        // Identify fragile depths for each word
154        for (int i = 0; i < n; i++) {
155            int currentNodeIndex = 0;
156          
157            for (char character : words[i].toCharArray()) {
158                int charIndex = character - 'a';
159                currentNodeIndex = trie.get(currentNodeIndex).children[charIndex];
160              
161                // This depth becomes fragile if count equals exactly k
162                if (trie.get(currentNodeIndex).count == k) {
163                    fragileDepths.get(i).add(trie.get(currentNodeIndex).depth);
164                }
165            }
166        }
167
168        // Use segment tree to efficiently find maximum valid depth
169        int segmentTreeSize = maxDepth;
170        if (segmentTreeSize >= 1) {
171            SegmentTree segmentTree = new SegmentTree(segmentTreeSize, globalCount);
172          
173            for (int i = 0; i < n; i++) {
174                if (n - 1 < k) {
175                    answer[i] = 0;
176                } else {
177                    // Temporarily decrease counts for fragile depths
178                    for (int depth : fragileDepths.get(i)) {
179                        segmentTree.update(1, 1, segmentTreeSize, depth, globalCount[depth] - 1);
180                    }
181                  
182                    // Query maximum valid depth
183                    int result = segmentTree.query();
184                    answer[i] = result == -1 ? 0 : result;
185                  
186                    // Restore original counts
187                    for (int depth : fragileDepths.get(i)) {
188                        segmentTree.update(1, 1, segmentTreeSize, depth, globalCount[depth]);
189                    }
190                }
191            }
192        }
193
194        return answer;
195    }
196}
197

1class Solution {
2public:
3    // Trie node structure to store prefix tree information
4    struct TrieNode {
5        int count = 0;           // Number of words passing through this node
6        int depth = 0;           // Depth of this node in the trie (length of prefix)
7        int children[26] = {0};  // Child node indices for each letter a-z
8    };
9
10    // Segment tree for efficient range maximum queries
11    class SegmentTree {
12    public:
13        int n;                       // Size of the segment tree
14        vector<int> tree;            // Segment tree array
15        vector<int>& globalCount;    // Reference to global count array
16      
17        // Constructor initializes segment tree with given size and count array
18        SegmentTree(int n, vector<int>& globalCount) 
19            : n(n), globalCount(globalCount) {
20            tree.assign(4 * (n + 1), -1);
21            build(1, 1, n);
22        }
23      
24        // Build segment tree recursively
25        void build(int nodeIdx, int left, int right) {
26            if (left == right) {
27                // Leaf node: store depth if count > 0, otherwise -1
28                tree[nodeIdx] = globalCount[left] > 0 ? left : -1;
29                return;
30            }
31            int mid = (left + right) / 2;
32            build(nodeIdx * 2, left, mid);
33            build(nodeIdx * 2 + 1, mid + 1, right);
34            // Internal node stores maximum of children
35            tree[nodeIdx] = max(tree[nodeIdx * 2], tree[nodeIdx * 2 + 1]);
36        }
37      
38        // Update a single position in the segment tree
39        void update(int nodeIdx, int left, int right, int position, int newValue) {
40            if (left == right) {
41                // Update leaf node based on new value
42                tree[nodeIdx] = newValue > 0 ? left : -1;
43                return;
44            }
45            int mid = (left + right) / 2;
46            if (position <= mid) {
47                update(nodeIdx * 2, left, mid, position, newValue);
48            } else {
49                update(nodeIdx * 2 + 1, mid + 1, right, position, newValue);
50            }
51            // Update internal node with maximum of children
52            tree[nodeIdx] = max(tree[nodeIdx * 2], tree[nodeIdx * 2 + 1]);
53        }
54      
55        // Query the maximum value in the entire range
56        int query() {
57            return tree[1];  // Root contains the maximum
58        }
59    };
60
61    vector<int> longestCommonPrefix(vector<string>& words, int k) {
62        int n = words.size();
63        vector<int> result(n, 0);
64      
65        // Early return if not enough words for k-common prefix
66        if (n - 1 < k) {
67            return result;
68        }
69      
70        // Build trie from all words
71        vector<TrieNode> trie(1);  // Initialize with root node
72        for (const string& word : words) {
73            int currentNode = 0;
74            for (char ch : word) {
75                int charIndex = ch - 'a';
76                // Create new node if path doesn't exist
77                if (trie[currentNode].children[charIndex] == 0) {
78                    trie[currentNode].children[charIndex] = trie.size();
79                    trie.push_back({0, trie[currentNode].depth + 1});
80                }
81                currentNode = trie[currentNode].children[charIndex];
82                trie[currentNode].count++;
83            }
84        }
85      
86        // Find maximum depth among nodes with count >= k
87        int maxDepth = 0;
88        for (int i = 1; i < trie.size(); ++i) {
89            if (trie[i].count >= k) {
90                maxDepth = max(maxDepth, trie[i].depth);
91            }
92        }
93      
94        // Count nodes at each depth that have count >= k
95        vector<int> globalCount(maxDepth + 1, 0);
96        for (int i = 1; i < trie.size(); ++i) {
97            if (trie[i].count >= k && trie[i].depth <= maxDepth) {
98                globalCount[trie[i].depth]++;
99            }
100        }
101      
102        // Find fragile depths for each word (nodes with exactly k occurrences)
103        vector<vector<int>> fragileDepths(n);
104        for (int i = 0; i < n; ++i) {
105            int currentNode = 0;
106            for (char ch : words[i]) {
107                int charIndex = ch - 'a';
108                currentNode = trie[currentNode].children[charIndex];
109                if (trie[currentNode].count == k) {
110                    fragileDepths[i].push_back(trie[currentNode].depth);
111                }
112            }
113        }
114      
115        // Process each word using segment tree if there are valid depths
116        int segmentSize = maxDepth;
117        if (segmentSize >= 1) {
118            SegmentTree segmentTree(segmentSize, globalCount);
119          
120            for (int i = 0; i < n; ++i) {
121                if (n - 1 < k) {
122                    result[i] = 0;
123                } else {
124                    // Temporarily decrease counts for fragile depths
125                    for (int depth : fragileDepths[i]) {
126                        segmentTree.update(1, 1, segmentSize, depth, globalCount[depth] - 1);
127                    }
128                  
129                    // Query maximum valid depth
130                    int maxValidDepth = segmentTree.query();
131                    result[i] = maxValidDepth == -1 ? 0 : maxValidDepth;
132                  
133                    // Restore original counts
134                    for (int depth : fragileDepths[i]) {
135                        segmentTree.update(1, 1, segmentSize, depth, globalCount[depth]);
136                    }
137                }
138            }
139        }
140      
141        return result;
142    }
143};
144

1// Trie node structure to store prefix tree information
2interface TrieNode {
3    count: number;           // Number of words passing through this node
4    depth: number;           // Depth of this node in the trie (length of prefix)
5    children: number[];      // Child node indices for each letter a-z (26 letters)
6}
7
8// Segment tree for efficient range maximum queries
9class SegmentTree {
10    private n: number;                    // Size of the segment tree
11    private tree: number[];               // Segment tree array
12    private globalCount: number[];        // Reference to global count array
13  
14    // Constructor initializes segment tree with given size and count array
15    constructor(n: number, globalCount: number[]) {
16        this.n = n;
17        this.globalCount = globalCount;
18        this.tree = new Array(4 * (n + 1)).fill(-1);
19        this.build(1, 1, n);
20    }
21  
22    // Build segment tree recursively
23    private build(nodeIdx: number, left: number, right: number): void {
24        if (left === right) {
25            // Leaf node: store depth if count > 0, otherwise -1
26            this.tree[nodeIdx] = this.globalCount[left] > 0 ? left : -1;
27            return;
28        }
29        const mid = Math.floor((left + right) / 2);
30        this.build(nodeIdx * 2, left, mid);
31        this.build(nodeIdx * 2 + 1, mid + 1, right);
32        // Internal node stores maximum of children
33        this.tree[nodeIdx] = Math.max(this.tree[nodeIdx * 2], this.tree[nodeIdx * 2 + 1]);
34    }
35  
36    // Update a single position in the segment tree
37    update(nodeIdx: number, left: number, right: number, position: number, newValue: number): void {
38        if (left === right) {
39            // Update leaf node based on new value
40            this.tree[nodeIdx] = newValue > 0 ? left : -1;
41            return;
42        }
43        const mid = Math.floor((left + right) / 2);
44        if (position <= mid) {
45            this.update(nodeIdx * 2, left, mid, position, newValue);
46        } else {
47            this.update(nodeIdx * 2 + 1, mid + 1, right, position, newValue);
48        }
49        // Update internal node with maximum of children
50        this.tree[nodeIdx] = Math.max(this.tree[nodeIdx * 2], this.tree[nodeIdx * 2 + 1]);
51    }
52  
53    // Query the maximum value in the entire range
54    query(): number {
55        return this.tree[1];  // Root contains the maximum
56    }
57}
58
59function longestCommonPrefix(words: string[], k: number): number[] {
60    const n = words.length;
61    const result: number[] = new Array(n).fill(0);
62  
63    // Early return if not enough words for k-common prefix
64    if (n - 1 < k) {
65        return result;
66    }
67  
68    // Build trie from all words
69    const trie: TrieNode[] = [
70        { count: 0, depth: 0, children: new Array(26).fill(0) }  // Initialize with root node
71    ];
72  
73    for (const word of words) {
74        let currentNode = 0;
75        for (const ch of word) {
76            const charIndex = ch.charCodeAt(0) - 'a'.charCodeAt(0);
77            // Create new node if path doesn't exist
78            if (trie[currentNode].children[charIndex] === 0) {
79                trie[currentNode].children[charIndex] = trie.length;
80                trie.push({
81                    count: 0,
82                    depth: trie[currentNode].depth + 1,
83                    children: new Array(26).fill(0)
84                });
85            }
86            currentNode = trie[currentNode].children[charIndex];
87            trie[currentNode].count++;
88        }
89    }
90  
91    // Find maximum depth among nodes with count >= k
92    let maxDepth = 0;
93    for (let i = 1; i < trie.length; i++) {
94        if (trie[i].count >= k) {
95            maxDepth = Math.max(maxDepth, trie[i].depth);
96        }
97    }
98  
99    // Count nodes at each depth that have count >= k
100    const globalCount: number[] = new Array(maxDepth + 1).fill(0);
101    for (let i = 1; i < trie.length; i++) {
102        if (trie[i].count >= k && trie[i].depth <= maxDepth) {
103            globalCount[trie[i].depth]++;
104        }
105    }
106  
107    // Find fragile depths for each word (nodes with exactly k occurrences)
108    const fragileDepths: number[][] = Array.from({ length: n }, () => []);
109    for (let i = 0; i < n; i++) {
110        let currentNode = 0;
111        for (const ch of words[i]) {
112            const charIndex = ch.charCodeAt(0) - 'a'.charCodeAt(0);
113            currentNode = trie[currentNode].children[charIndex];
114            if (trie[currentNode].count === k) {
115                fragileDepths[i].push(trie[currentNode].depth);
116            }
117        }
118    }
119  
120    // Process each word using segment tree if there are valid depths
121    const segmentSize = maxDepth;
122    if (segmentSize >= 1) {
123        const segmentTree = new SegmentTree(segmentSize, globalCount);
124      
125        for (let i = 0; i < n; i++) {
126            if (n - 1 < k) {
127                result[i] = 0;
128            } else {
129                // Temporarily decrease counts for fragile depths
130                for (const depth of fragileDepths[i]) {
131                    segmentTree.update(1, 1, segmentSize, depth, globalCount[depth] - 1);
132                }
133              
134                // Query maximum valid depth
135                const maxValidDepth = segmentTree.query();
136                result[i] = maxValidDepth === -1 ? 0 : maxValidDepth;
137              
138                // Restore original counts
139                for (const depth of fragileDepths[i]) {
140                    segmentTree.update(1, 1, segmentSize, depth, globalCount[depth]);
141                }
142            }
143        }
144    }
145  
146    return result;
147}
148

Time and Space Complexity

Time Complexity: O(n * m + n * f * log(m))

Breaking down the time complexity:

Building the Trie: O(n * m) where n is the number of words and m is the average length of each word
Traversing the Trie to calculate maxDepth and globalCount: O(T) where T is the total number of nodes in the Trie, which is at most O(n * m)
Building the fragile list: O(n * m) as we traverse each word again
Building the Segment Tree: O(maxDepth) which is at most O(m)
For each word, updating and querying the Segment Tree: O(n * f * log(maxDepth)) where f is the average number of fragile nodes per word, and each update/query takes O(log(maxDepth)) time

The dominant term is O(n * m) for simple cases, but when there are many fragile nodes, the segment tree operations become significant, resulting in O(n * m + n * f * log(m)).

Space Complexity: O(n * m)

Breaking down the space complexity:

Trie storage: O(n * m) in the worst case where all words have unique prefixes
Each TrieNode contains an array of size 26, so the actual space is O(26 * T) where T is the number of Trie nodes
Segment Tree: O(4 * maxDepth) which is O(m)
globalCount array: O(maxDepth) which is O(m)
fragileList: O(n * f) where f is the average number of fragile nodes per word
Answer array: O(n)

The dominant term is the Trie storage at O(n * m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Empty Fragile Depths

Pitfall: When a word doesn't pass through any nodes with exactly k count (no fragile nodes), the code still processes the segment tree update/restore loop with an empty list. While this doesn't cause errors, it can lead to confusion about whether the answer should be the global maximum or 0.

Example Scenario:

words = ["ab", "abc", "abcd", "abcde"], k = 2
The word "abcde" might not have any fragile nodes if all its prefix nodes have count > k

Solution: Explicitly handle the case when there are no fragile depths:

for i in range(n):
    if n - 1 < k:
        result[i] = 0
    elif len(fragile_depths[i]) == 0:
        # No fragile nodes means removing this word doesn't affect any k-threshold
        # Simply query the current maximum
        result[i] = segment_tree.query()
        result[i] = 0 if result[i] == -1 else result[i]
    else:
        # Process fragile depths as before
        for depth in fragile_depths[i]:
            segment_tree.update(1, 1, segment_size, depth, global_count[depth] - 1)
        max_valid_depth = segment_tree.query()
        result[i] = 0 if max_valid_depth == -1 else max_valid_depth
        for depth in fragile_depths[i]:
            segment_tree.update(1, 1, segment_size, depth, global_count[depth])

2. Off-by-One Error in Segment Tree Indexing

Pitfall: The segment tree uses 1-based indexing for depths (1 to max_depth), but Python lists are 0-indexed. Mixing these can cause accessing invalid indices or missing depth 0.

Example Issue: If global_count is 0-indexed but segment tree expects 1-indexed depths, global_count[0] might be ignored.

Solution: Ensure consistent indexing throughout:

# Option 1: Make global_count 1-indexed by padding with dummy value at index 0
global_count = [0] * (max_depth + 1)  # Current approach is correct

# Option 2: Adjust segment tree to handle 0-indexed arrays
class SegmentTree:
    def __init__(self, n: int, global_count: List[int]):
        self.n = n
        self.global_count = global_count
        self.tree = [-1] * (4 * (n + 1))
        if n >= 1:
            self.build(1, 0, n - 1)  # Use 0-based range

3. Missing Edge Case: All Words Share No Common Prefix with k Others

Pitfall: If no depth has at least k nodes (meaning no prefix is shared by at least k words), max_depth remains 0, and the segment tree might not be properly initialized.

Example: words = ["a", "b", "c", "d"], k = 2 - no two words share any prefix.

Solution: Add explicit check for this case:

# After calculating max_depth
if max_depth == 0:
    # No valid prefixes exist with count >= k
    return [0] * n

# Continue with segment tree construction only if max_depth > 0

4. Memory Optimization Overlooked for Large Alphabets

Pitfall: The original Java solution uses fixed-size arrays for children (children[26]), but the Python version uses dictionaries. While more memory-efficient for sparse tries, dictionary operations are slightly slower.

Trade-off Consideration: For problems with full lowercase alphabet usage, consider using lists:

# Instead of: 'children': {}
# Consider: 'children': [-1] * 26  # for lowercase letters only

# Then access would be:
char_index = ord(ch) - ord('a')
if trie[current_node]['children'][char_index] == -1:
    trie[current_node]['children'][char_index] = len(trie)
    # Create new node

This trades memory for speed but should be chosen based on the specific constraints and character set size.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don't know