Longest Common Prefix Between Adjacent Strings After Removals - Video Solutions
3598. Longest Common Prefix Between Adjacent Strings After Removals | Weekly Contest 456š„ | Java
Longest Common Prefix Between Adjacent Strings After Removals - Video Solution
Watch 7 video solutions for Longest Common Prefix Between Adjacent Strings After Removals, a medium level problem involving Array, String. This walkthrough by ExpertFunda has 838 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an array of strings words. For each index i in the range [0, words.length - 1], perform the following steps:
- Remove the element at index
ifrom thewordsarray. - Compute the length of the longest common prefix among all adjacent pairs in the modified 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:
- Removing index 0:
wordsbecomes["run", "run", "jump", "run"]- Longest adjacent pair is
["run", "run"]having a common prefix"run"(length 3)
- Removing index 1:
wordsbecomes["jump", "run", "jump", "run"]- No adjacent pairs share a common prefix (length 0)
- Removing index 2:
wordsbecomes["jump", "run", "jump", "run"]- No adjacent pairs share a common prefix (length 0)
- Removing index 3:
wordsbecomes["jump", "run", "run", "run"]- Longest adjacent pair is
["run", "run"]having a common prefix"run"(length 3)
- Removing index 4:
- words becomes
["jump", "run", "run", "jump"] - Longest adjacent pair is
["run", "run"]having a common prefix"run"(length 3)
- words becomes
Example 2:
Input: words = ["dog","racer","car"]
Output: [0,0,0]
Explanation:
- Removing any index results in an answer of 0.
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 104words[i]consists of lowercase English letters.- The sum of
words[i].lengthis smaller than or equal105.
Approach Overview
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).
Complexity Analysis
| 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 |