Facebook Pixel

3485. Longest Common Prefix of K Strings After Removal

HardTrieArrayString
Leetcode Link

Problem Description

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 array after removing the i-th element. Return an array answer, where answer[i] is the answer for the i-th element. If removing the i-th element leaves the array with fewer than k strings, answer[i] is 0.

Intuition

To solve this problem, we need to determine the longest common prefix that appears among any k strings in the words array after removing each word one at a time. A trie data structure is suitable for this task as it efficiently manages the prefixes of strings.

  1. Trie Construction: First, construct a trie with all the words in the words array. Each node in the trie keeps track of how many words pass through it. This is accomplished by incrementing a counter each time a word passes through a node corresponding to the character being processed.

  2. Counting Nodes by Depth: Traverse through the trie to determine the maximum depth where at least k words share the same prefix. This depth represents the length of the longest prefix common to at least k strings. We maintain an array globalCount that records how many nodes at each depth have at least k words passing through them.

  3. Handling Removals: For each word, determine which nodes in the trie are "fragile," meaning their removal changes the prefix count at particular depths. Use a SegmentTree to efficiently manage and update the globalCount array. For each word removed, update the segment tree to reflect its removal, query the maximum valid prefix length, and then restore the tree back to its original state.

  4. Efficient Querying: The segment tree provides efficient queries and updates, ensuring the solution remains performant even as we repeatedly remove and reinsert words.

Learn more about Trie patterns.

Solution Approach

The solution utilizes a combination of data structures to manage and efficiently compute the longest common prefix after removing each word. Here is a step-by-step breakdown of the approach:

  1. Data Structures Used:

    • Trie Data Structure:
      • Construct a TrieNode class that contains:
        • count: a counter for words passing through this node.
        • depth: the depth of this node in the trie.
        • children: an array to store references to child nodes (for 26 lowercase English letters).
    • Segment Tree:
      • Used for efficient updates and queries on the lengths of common prefixes after removing each word.
      • Implemented with a tree of size 4 * (n + 1) where n is the maximum depth in the trie.

  2. Building the Trie:

    • For each word in words, insert it into the trie.
    • As each character in the word is traversed, increment the count at the corresponding node and assign the appropriate depth.

  3. Calculate Global Count for Depths:

    • Traverse each node in the trie and populate globalCount array, tracking how deep a common prefix exists for at least k words.

  4. Manage Fragile Nodes:

    • For each word, identify nodes (or depths) that become "fragile" upon its removal, meaning these depths will no longer maintain the prefix condition with k counts.
    • These nodes are tracked using a fragileList.

  5. Utilize Segment Tree:

    • Initialize the SegmentTree with globalCount to keep track of feasible prefix depths.
    • For each word removal, update the segment tree according to the affected fragile depths, query the maximum feasible prefix length, and then restore the tree state.
    • Each query yields the longest prefix length achievable after removing that specific word.

  6. Return Results:

    • Compile and return the results for each query in an array, where each position gives the longest prefix length possible after a specific word is removed.

This method ensures an efficient algorithm, leveraging the trie for prefix management and the segment tree for real-time updates during each word removal scenario.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have the array of strings words = ["apple", "apply", "ape", "apricot"] and an integer k = 2. We want to compute the longest common prefix of any k words from the array after removing each word once.

Step-by-step Process:

  1. Construct the Trie:

    • Insert each word from words into a trie. Here's a simplified view of the trie:
      • a
        • p
          • p
            • l
              • e (apple)
              • y (apply)
          • e (ape)
        • p
          • r
            • i
              • c
                • o
                  • t (apricot)
    • Count how many words pass through each node.

  2. Calculate Global Node Counts:

    • Traverse the trie to calculate globalCount: how many nodes at each depth have at least k words passing through. For instance, all first-level (root) nodes are passed by all words, second-level (node p under a) by all but apricot, and so forth.

  3. Manage Removals and Calculate Prefix Lengths:

    • For each word, determine the nodes that would be affected ("fragile") if the word were removed. For example:
      • Removing "apple" means node e at depth 5 becomes fragile because apple adds to the prefix ending at e.
    • Update a segment tree to reflect these changes and query the new maximum prefix length. For instance:
      • Removing "apple" might leave "apply" and "ape" giving a common prefix "ap".
    • Conduct updates and restorations on the segment tree efficiently.

  4. Compute and return the results:

    • Perform the above computations for each word removal:
      • For "apple," longest prefix after removal is 2 (from "apply", "ape").
      • For "apply," longest prefix keeps ap from "apple", "ape".
      • For "ape," longest prefix keeps ap from "apple", "apply".
      • For "apricot," longest prefix is appl from "apple", "apply".

Final output for answer will be [2, 2, 2, 4], which indicates the longest common prefix lengths after removing each word one at a time.

Solution Implementation

1class TrieNode:
2    def __init__(self):
3        self.count = 0  # Count of words having this prefix
4        self.depth = 0  # Depth of the node in the trie
5        self.children = [0] * 26  # References to child nodes
6
7class SegmentTree:
8    def __init__(self, n, global_count):
9        self.n = n  # Size of the segment tree
10        self.tree = [-1] * (4 * (n + 1))  # Initialize the segment tree with -1
11        self.global_count = global_count  # Reference to the global count vector
12        self.build(1, 1, n)  # Build the tree starting at index 1
13
14    def build(self, index, left, right):
15        # Recursive build function for the segment tree
16        if left == right:
17            # Leaf node
18            self.tree[index] = left if self.global_count[left] > 0 else -1
19            return
20        mid = (left + right) // 2
21        self.build(index * 2, left, mid)  # Build left subtree
22        self.build(index * 2 + 1, mid + 1, right)  # Build right subtree
23        self.tree[index] = max(self.tree[index * 2], self.tree[index * 2 + 1])  # Set the parent node value
24
25    def update(self, index, left, right, position, new_value):
26        # Update the segment tree at a specific position
27        if left == right:
28            # Leaf node update
29            self.tree[index] = left if new_value > 0 else -1
30            return
31        mid = (left + right) // 2
32        if position <= mid:
33            self.update(index * 2, left, mid, position, new_value)  # Update left subtree
34        else:
35            self.update(index * 2 + 1, mid + 1, right, position, new_value)  # Update right subtree
36        self.tree[index] = max(self.tree[index * 2], self.tree[index * 2 + 1])  # Update parent node value
37
38    def query(self):
39        # Query the maximum value from the segment tree
40        return self.tree[1]  # Return the root which contains the maximum value
41
42class Solution:
43    def longestCommonPrefix(self, words, k):
44        n = len(words)
45        result = [0] * n  # Initialize result list with 0s
46
47        if n - 1 < k:
48            return result  # Quick exit if there are not enough words
49
50        trie = [TrieNode()]  # Initialize a trie with root node
51
52        # Build the trie with word data
53        for word in words:
54            current_node = 0
55            for c in word:
56                index = ord(c) - ord('a')  # Calculate char index
57                if trie[current_node].children[index] == 0:
58                    trie[current_node].children[index] = len(trie)
59                    trie.append(TrieNode())
60                    trie[-1].depth = trie[current_node].depth + 1
61                current_node = trie[current_node].children[index]
62                trie[current_node].count += 1
63
64        max_depth = 0  # Maximum depth where any node has count >= k
65
66        # Determine the maximum depth with sufficient frequency
67        for node in trie[1:]:
68            if node.count >= k:
69                max_depth = max(max_depth, node.depth)
70
71        global_count = [0] * (max_depth + 1)  # Frequency of nodes at each depth
72
73        # Calculate frequency of depths
74        for node in trie[1:]:
75            if node.count >= k and node.depth <= max_depth:
76                global_count[node.depth] += 1
77
78        fragile_list = [[] for _ in range(n)]  # List to store fragile nodes for each word
79
80        # Assign depths to fragile_list for each word
81        for i, word in enumerate(words):
82            current_node = 0
83            for c in word:
84                index = ord(c) - ord('a')
85                current_node = trie[current_node].children[index]
86                if trie[current_node].count == k:
87                    fragile_list[i].append(trie[current_node].depth)
88
89        seg_size = max_depth  # Segment size for segment tree
90
91        if seg_size >= 1:
92            segment_tree = SegmentTree(seg_size, global_count)  # Initialize the segment tree
93
94            for i in range(n):
95                if n - 1 < k:
96                    result[i] = 0
97                else:
98                    # Update segment tree for current word's fragile nodes
99                    for depth in fragile_list[i]:
100                        segment_tree.update(1, 1, seg_size, depth, global_count[depth] - 1)
101                    # Query for the longest common prefix
102                    res = segment_tree.query()
103                    result[i] = 0 if res == -1 else res
104                    # Restore updates
105                    for depth in fragile_list[i]:
106                        segment_tree.update(1, 1, seg_size, depth, global_count[depth])
107
108        return result  # Return the result list
109
1class Solution {
2    // Define TrieNode class to represent each node in the Trie data structure
3    static class TrieNode {
4        int count = 0; // Count of words passing through this node
5        int depth = 0; // Depth of the node in the Trie tree
6        int[] children = new int[26]; // Pointers to children nodes for each alphabetical letter
7
8        TrieNode() {
9            // Initialize all children pointers to -1
10            for (int i = 0; i < 26; ++i) children[i] = -1;
11        }
12    }
13
14    // Define SegmentTree class to handle segment tree operations
15    static class SegmentTree {
16        int n; // Number of elements this segment tree manages (based on depth)
17        int[] tree; // Segment tree array
18        int[] globalCount; // Count of nodes at each depth that have at least 'k' words
19
20        SegmentTree(int n, int[] globalCount) {
21            this.n = n;
22            this.globalCount = globalCount;
23            this.tree = new int[4 * (n + 1)]; // Allocate space for the segment tree
24            for (int i = 0; i < tree.length; i++) tree[i] = -1; // Initialize the tree
25            build(1, 1, n); // Build the initial segment tree
26        }
27
28        // Build the segment tree recursively
29        void build(int idx, int left, int right) {
30            if (left == right) {
31                tree[idx] = globalCount[left] > 0 ? left : -1; // Assign depth if count is positive
32                return;
33            }
34            int mid = (left + right) / 2;
35            build(idx * 2, left, mid); // Build left subtree
36            build(idx * 2 + 1, mid + 1, right); // Build right subtree
37            tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]); // Update current node with maximum depth of children
38        }
39
40        // Update the segment tree with new values
41        void update(int idx, int left, int right, int pos, int newVal) {
42            if (left == right) {
43                tree[idx] = newVal > 0 ? left : -1; // Update the depth at position
44                return;
45            }
46            int mid = (left + right) / 2;
47            if (pos <= mid) {
48                update(idx * 2, left, mid, pos, newVal); // Update left subtree
49            } else {
50                update(idx * 2 + 1, mid + 1, right, pos, newVal); // Update right subtree
51            }
52            tree[idx] = Math.max(tree[idx * 2], tree[idx * 2 + 1]); // Update current node with maximum depth of children
53        }
54
55        // Query for the longest common prefix depth
56        int query() {
57            return tree[1]; // The root of the segment tree holds the answer
58        }
59    }
60
61    // Main method to compute longest common prefix for each word with at least k occurrences
62    public int[] longestCommonPrefix(String[] words, int k) {
63        int n = words.length;
64        int[] ans = new int[n]; // Array to store the results for each word
65        if (n - 1 < k) return ans; // If not enough words, return an array of zeros
66
67        ArrayList<TrieNode> trie = new ArrayList<>();
68        trie.add(new TrieNode()); // Initialize the trie with a root node
69
70        // Build the Trie with word occurrences
71        for (String word : words) {
72            int cur = 0;
73            for (char c : word.toCharArray()) {
74                int idx = c - 'a';
75                if (trie.get(cur).children[idx] == -1) {
76                    trie.get(cur).children[idx] = trie.size();
77                    TrieNode node = new TrieNode();
78                    node.depth = trie.get(cur).depth + 1;
79                    trie.add(node);
80                }
81                cur = trie.get(cur).children[idx];
82                trie.get(cur).count++;
83            }
84        }
85
86        int maxDepth = 0;
87        // Determine the maximum depth with at least k occurrences
88        for (int i = 1; i < trie.size(); ++i) {
89            if (trie.get(i).count >= k) {
90                maxDepth = Math.max(maxDepth, trie.get(i).depth);
91            }
92        }
93
94        int[] globalCount = new int[maxDepth + 1];
95        // Count how many nodes are at each depth meeting the k criteria
96        for (int i = 1; i < trie.size(); ++i) {
97            TrieNode node = trie.get(i);
98            if (node.count >= k && node.depth <= maxDepth) {
99                globalCount[node.depth]++;
100            }
101        }
102
103        List<List<Integer>> fragileList = new ArrayList<>();
104        // Initialize list to store significant depths for each word
105        for (int i = 0; i < n; ++i) {
106            fragileList.add(new ArrayList<>());
107        }
108
109        // Populate each word's significant depths
110        for (int i = 0; i < n; ++i) {
111            int cur = 0;
112            for (char c : words[i].toCharArray()) {
113                int idx = c - 'a';
114                cur = trie.get(cur).children[idx];
115                if (trie.get(cur).count == k) {
116                    fragileList.get(i).add(trie.get(cur).depth);
117                }
118            }
119        }
120
121        int segSize = maxDepth;
122        // Build and use segment tree to find results for each word
123        if (segSize >= 1) {
124            SegmentTree segTree = new SegmentTree(segSize, globalCount);
125            for (int i = 0; i < n; ++i) {
126                if (n - 1 < k) {
127                    ans[i] = 0;
128                } else {
129                    // Update and query the segment tree for each word
130                    for (int d : fragileList.get(i)) {
131                        segTree.update(1, 1, segSize, d, globalCount[d] - 1);
132                    }
133                    int res = segTree.query();
134                    ans[i] = res == -1 ? 0 : res;
135                    for (int d : fragileList.get(i)) {
136                        segTree.update(1, 1, segSize, d, globalCount[d]);
137                    }
138                }
139            }
140        }
141
142        return ans; // Return the results array
143    }
144}
145
1#include <vector>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    struct TrieNode {
10        int count = 0; // Count of words having this prefix
11        int depth = 0; // Depth of the node in the trie
12        int children[26] = {0}; // References to child nodes
13    };
14
15    // Segment Tree class for range maximum query and updating
16    class SegmentTree {
17    public:
18        int n; // Size of the segment tree
19        vector<int> tree; // Segment tree structure
20        vector<int>& globalCount; // Reference to the global count vector
21
22        // Constructor to initialize segment tree
23        SegmentTree(int n, vector<int>& globalCount)
24            : n(n), globalCount(globalCount) {
25            tree.assign(4 * (n + 1), -1); // Initialize the tree with -1
26            build(1, 1, n); // Build the tree starting at index 1
27        }
28
29        // Recursive build function for the segment tree
30        void build(int index, int left, int right) {
31            if (left == right) {
32                // Leaf node
33                tree[index] = globalCount[left] > 0 ? left : -1;
34                return;
35            }
36            int mid = (left + right) / 2;
37            build(index * 2, left, mid); // Build left subtree
38            build(index * 2 + 1, mid + 1, right); // Build right subtree
39            tree[index] = max(tree[index * 2], tree[index * 2 + 1]); // Set the parent node value
40        }
41
42        // Update the segment tree at a specific position
43        void update(int index, int left, int right, int position, int newValue) {
44            if (left == right) {
45                // Leaf node update
46                tree[index] = newValue > 0 ? left : -1;
47                return;
48            }
49            int mid = (left + right) / 2;
50            if (position <= mid)
51                update(index * 2, left, mid, position, newValue); // Update left subtree
52            else
53                update(index * 2 + 1, mid + 1, right, position, newValue); // Update right subtree
54            tree[index] = max(tree[index * 2], tree[index * 2 + 1]); // Update parent node value
55        }
56
57        // Query the maximum value from the segment tree
58        int query() {
59            return tree[1]; // Return the root which contains the maximum value
60        }
61    };
62
63    // Function to calculate the longest common prefix of words with at least k occurrences
64    vector<int> longestCommonPrefix(vector<string>& words, int k) {
65        int n = words.size();
66        vector<int> result(n, 0); // Initialize result vector with 0s
67
68        if (n - 1 < k) return result; // Quick exit if there are not enough words
69
70        vector<TrieNode> trie(1); // Initialize a trie with root node
71
72        // Build the trie with word data
73        for (const string& word : words) {
74            int currentNode = 0;
75            for (char c : word) {
76                int index = c - 'a'; // Calculate char index
77                if (trie[currentNode].children[index] == 0) {
78                    trie[currentNode].children[index] = trie.size();
79                    trie.push_back({0, trie[currentNode].depth + 1});
80                }
81                currentNode = trie[currentNode].children[index];
82                trie[currentNode].count++;
83            }
84        }
85
86        int maxDepth = 0; // Maximum depth where any node has count >= k
87
88        // Determine the maximum depth with sufficient frequency
89        for (int i = 1; i < trie.size(); ++i) {
90            if (trie[i].count >= k) {
91                maxDepth = max(maxDepth, trie[i].depth);
92            }
93        }
94
95        vector<int> globalCount(maxDepth + 1, 0); // Frequency of nodes at each depth
96
97        // Calculate frequency of depths
98        for (int i = 1; i < trie.size(); ++i) {
99            if (trie[i].count >= k && trie[i].depth <= maxDepth) {
100                globalCount[trie[i].depth]++;
101            }
102        }
103
104        vector<vector<int>> fragileList(n); // List to store fragile nodes for each word
105
106        // Assign depths to fragileList for each word
107        for (int i = 0; i < n; ++i) {
108            int currentNode = 0;
109            for (char c : words[i]) {
110                int index = c - 'a';
111                currentNode = trie[currentNode].children[index];
112                if (trie[currentNode].count == k) {
113                    fragileList[i].push_back(trie[currentNode].depth);
114                }
115            }
116        }
117
118        int segSize = maxDepth; // Segment size for segment tree
119
120        if (segSize >= 1) {
121            SegmentTree segmentTree(segSize, globalCount); // Initialize the segment tree
122
123            for (int i = 0; i < n; ++i) {
124                if (n - 1 < k) {
125                    result[i] = 0;
126                } else {
127                    // Update segment tree for current word's fragile nodes
128                    for (int depth : fragileList[i]) {
129                        segmentTree.update(1, 1, segSize, depth, globalCount[depth] - 1);
130                    }
131                    // Query for the longest common prefix
132                    int res = segmentTree.query();
133                    result[i] = res == -1 ? 0 : res;
134                    // Restore updates
135                    for (int depth : fragileList[i]) {
136                        segmentTree.update(1, 1, segSize, depth, globalCount[depth]);
137                    }
138                }
139            }
140        }
141
142        return result; // Return the result vector
143    }
144};
145
1type TrieNode = {
2    count: number; // Count of words having this prefix
3    depth: number; // Depth of the node in the trie
4    children: number[]; // References to child nodes
5};
6
7// Initialize a trie node
8function createTrieNode(depth: number): TrieNode {
9    return {
10        count: 0,
11        depth: depth,
12        children: Array(26).fill(0)
13    };
14}
15
16// Segment Tree for range maximum queries and updates
17class SegmentTree {
18    private n: number; // Size of the segment tree
19    private tree: number[]; // Segment tree structure
20    private globalCount: number[]; // Reference to the global count array
21
22    // Constructor to initialize segment tree
23    constructor(n: number, globalCount: number[]) {
24        this.n = n;
25        this.globalCount = globalCount;
26        this.tree = new Array(4 * (n + 1)).fill(-1); // Initialize the tree with -1
27        this.build(1, 1, n); // Build the tree starting at index 1
28    }
29
30    // Recursive build function for the segment tree
31    private build(index: number, left: number, right: number) {
32        if (left === right) {
33            // Leaf node
34            this.tree[index] = this.globalCount[left] > 0 ? left : -1;
35            return;
36        }
37      
38        const mid = Math.floor((left + right) / 2);
39        this.build(index * 2, left, mid); // Build left subtree
40        this.build(index * 2 + 1, mid + 1, right); // Build right subtree
41        this.tree[index] = Math.max(this.tree[index * 2], this.tree[index * 2 + 1]); // Set the parent node value
42    }
43
44    // Update the segment tree at a specific position
45    update(index: number, left: number, right: number, position: number, newValue: number) {
46        if (left === right) {
47            // Leaf node update
48            this.tree[index] = newValue > 0 ? left : -1;
49            return;
50        }
51      
52        const mid = Math.floor((left + right) / 2);
53        if (position <= mid)
54            this.update(index * 2, left, mid, position, newValue); // Update left subtree
55        else
56            this.update(index * 2 + 1, mid + 1, right, position, newValue); // Update right subtree
57
58        this.tree[index] = Math.max(this.tree[index * 2], this.tree[index * 2 + 1]); // Update parent node value
59    }
60
61    // Query the maximum value from the segment tree
62    query(): number {
63        return this.tree[1]; // Return the root which contains the maximum value
64    }
65}
66
67// Function to calculate the longest common prefix of words with at least k occurrences
68function longestCommonPrefix(words: string[], k: number): number[] {
69    const n = words.length;
70    const result = new Array(n).fill(0); // Initialize result array with 0s
71
72    // Quick exit if there are not enough words
73    if (n - 1 < k) return result;
74
75    const trie: TrieNode[] = [createTrieNode(0)]; // Initialize the trie with root node
76
77    // Build the trie with word data
78    for (const word of words) {
79        let currentNode = 0;
80        for (const c of word) {
81            const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
82            if (trie[currentNode].children[index] === 0) {
83                trie[currentNode].children[index] = trie.length;
84                trie.push(createTrieNode(trie[currentNode].depth + 1));
85            }
86            currentNode = trie[currentNode].children[index];
87            trie[currentNode].count++;
88        }
89    }
90
91    let maxDepth = 0; // Maximum depth where any node has count >= k
92
93    // Determine the maximum depth with sufficient frequency
94    for (let i = 1; i < trie.length; ++i) {
95        if (trie[i].count >= k) {
96            maxDepth = Math.max(maxDepth, trie[i].depth);
97        }
98    }
99
100    const globalCount = new Array(maxDepth + 1).fill(0); // Frequency of nodes at each depth
101
102    // Calculate frequency of depths
103    for (let i = 1; i < trie.length; ++i) {
104        if (trie[i].count >= k && trie[i].depth <= maxDepth) {
105            globalCount[trie[i].depth]++;
106        }
107    }
108
109    const fragileList: number[][] = Array.from({ length: n }, () => []); // List to store fragile nodes for each word
110
111    // Assign depths to fragileList for each word
112    for (let i = 0; i < n; ++i) {
113        let currentNode = 0;
114        for (const c of words[i]) {
115            const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
116            currentNode = trie[currentNode].children[index];
117            if (trie[currentNode].count === k) {
118                fragileList[i].push(trie[currentNode].depth);
119            }
120        }
121    }
122
123    const segSize = maxDepth; // Segment size for segment tree
124
125    if (segSize >= 1) {
126        const segmentTree = new SegmentTree(segSize, globalCount); // Initialize the segment tree
127
128        for (let i = 0; i < n; ++i) {
129            if (n - 1 < k) {
130                result[i] = 0;
131            } else {
132                // Update segment tree for current word's fragile nodes
133                for (const depth of fragileList[i]) {
134                    segmentTree.update(1, 1, segSize, depth, globalCount[depth] - 1);
135                }
136                // Query for the longest common prefix
137                const res = segmentTree.query();
138                result[i] = res === -1 ? 0 : res;
139                // Restore updates
140                for (const depth of fragileList[i]) {
141                    segmentTree.update(1, 1, segSize, depth, globalCount[depth]);
142                }
143            }
144        }
145    }
146
147    return result; // Return the result array
148}
149

Time and Space Complexity

The main tasks within the code include building a trie, constructing a segment tree, and iterating over the words multiple times to perform different operations. Let's break down the complexities.

Time Complexity

  1. Building the Trie:

    • For each word, each character is processed to construct the trie, which is O(L), where L is the total number of characters across all words.
    • Therefore, building the trie has a time complexity of O(L).

  2. Filling the Global Count:

    • For each node in the trie, it checks whether the count is greater than or equal to k and increments the global count accordingly.
    • This complexity is O(M), where M is the number of nodes in the trie, which is at most O(L).

  3. Constructing the Segment Tree:

    • Building the segment tree and initializing it requires O(D), where D is the maximum depth of the trie (maxDepth).

  4. Updating and Querying the Segment Tree:

    • Each word results in D updates and queries in the segment tree, leading to the operations cost being O(D log D) for each word.

  5. Total Complexity:

    • Summing up all the tasks, the total time complexity becomes O(L + nD log D), where n is the number of words, L is the total length of all words, and D is the maximum depth of the trie.

Space Complexity

  1. Trie Construction:

    • The space required for the trie is proportional to the number of nodes, which is O(L).

  2. Global Count Array:

    • The size of this array is O(D).

  3. Segment Tree:

    • The segment tree requires O(D) space.

  4. Other Data Structures:

    • Arrays and lists used for storing results and intermediates also contribute to the space but remain within these bounds.

  5. Total Complexity:

    • Thus, the total space complexity can be estimated as O(L + D).

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

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

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Trie Introduction

Trie Introduction Imagine you have a magic dictionary where as soon as you start spelling a word it immediately tells you how many words that start with those letters How cool would that be This is exactly the kind of magic a data structure called trie performs What's a Trie

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More