You are given an array of strings words. For each index i in the range [0, words.length - 1], perform the following steps:
i from the words array.Return an array answer, where answer[i] is the length of the longest common prefix between the adjacent pairs after removing the element at index i. If no adjacent pairs remain or if none share a common prefix, then answer[i] should be 0.
Example 1:
Input: words = ["jump","run","run","jump","run"]
Output: [3,0,0,3,3]
Explanation:
words becomes ["run", "run", "jump", "run"]["run", "run"] having a common prefix "run" (length 3)words becomes ["jump", "run", "jump", "run"]words becomes ["jump", "run", "jump", "run"]words becomes ["jump", "run", "run", "run"]["run", "run"] having a common prefix "run" (length 3)["jump", "run", "run", "jump"]["run", "run"] having a common prefix "run" (length 3)Example 2:
Input: words = ["dog","racer","car"]
Output: [0,0,0]
Explanation:
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 104words[i] consists of lowercase English letters.words[i].length is smaller than or equal 105.Problem Overview: You are given an array of strings. After removing a string, the adjacency between remaining strings changes. The task is to determine the maximum longest common prefix (LCP) between any pair of adjacent strings after each removal.
Approach 1: Recompute Adjacent LCP After Each Removal (Brute Force) (Time: O(n2 * m), Space: O(1))
Simulate every removal and recompute the longest common prefix for all adjacent pairs in the remaining array. For each pair, iterate character by character until characters differ. If the average string length is m, each LCP calculation costs O(m), and there are up to O(n) pairs per simulation. This approach is straightforward but inefficient because the entire array is rescanned after every removal.
Approach 2: Ordered Set with Dynamic LCP Updates (Time: O(n log n + k · m), Space: O(n))
Maintain an ordered set of active indices representing the current string order. Precompute the LCP between every original adjacent pair using a helper function that scans characters until they differ. Store these values in a structure that can quickly track the maximum, such as a multiset or priority container.
When a string at index i is removed, only the neighboring relationships change. Remove the LCP values for pairs (i-1, i) and (i, i+1). Then compute a new LCP for the new adjacent pair (i-1, i+1) and insert it into the set. Because only local neighbors are affected, each update requires O(log n) ordered-set operations plus O(m) time to compute the new prefix length.
This technique avoids recomputing all adjacent pairs. The ordered structure efficiently tracks neighbors, and the multiset allows quick retrieval of the maximum LCP after each update.
The solution relies on common operations from array indexing and string prefix comparison from string problems. The ordered index maintenance resembles techniques used with balanced trees or ordered containers.
Recommended for interviews: The ordered set approach. Interviewers want to see that you recognize only local adjacency changes after a removal. Recomputing everything shows basic understanding, but maintaining neighbor relationships with an ordered structure demonstrates stronger algorithmic thinking and reduces the complexity to roughly O(n log n).
We define a function calc(s, t), which calculates the length of the longest common prefix between strings s and t. We can use an ordered set to maintain the longest common prefix lengths of all adjacent string pairs.
Define a function add(i, j), which adds the longest common prefix length of the string pair at indices i and j to the ordered set. Define a function remove(i, j), which removes the longest common prefix length of the string pair at indices i and j from the ordered set.
First, we compute the longest common prefix lengths for all adjacent string pairs and store them in the ordered set. Then, for each index i, we perform the following steps:
i and i + 1.i - 1 and i.i - 1 and i + 1.i - 1 and i + 1.i - 1 and i.i and i + 1.In this way, after removing each string, we can quickly compute the longest common prefix length between adjacent string pairs.
The time complexity is O(L + n times log n), and the space complexity is O(n), where L is the total length of all strings and n is the number of strings.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute After Each Removal (Brute Force) | O(n² · m) | O(1) | Small input sizes or quick prototype implementation |
| Ordered Set with Dynamic LCP Tracking | O(n log n + k · m) | O(n) | General case where removals change adjacency and fast updates are required |
3598. Longest Common Prefix Between Adjacent Strings After Removals | Weekly Contest 456🔥 | Java • ExpertFunda • 832 views views
Watch 8 more video solutions →Practice Longest Common Prefix Between Adjacent Strings After Removals with our built-in code editor and test cases.
Practice on FleetCode