3598. Longest Common Prefix Between Adjacent Strings After Removals
Medium32.3% acceptance18,990 / 58,732 submissions
Asked by 1 company
Topics
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.
Hints
Hint 1
Precompute the longest common prefix length for adjacent prefixes and suffixes.
Hint 2
After deleting
words[i], compute the longest common prefix for words[i - 1] and words[i + 1] (if they exist).Hint 3
Use the result of the prefix computation up to
i - 1 and the suffix computation from i + 1 onwards.