#3598

Medium

LeetCode Problem Workspace

Longest Common Prefix Between Adjacent Strings After Removals

Given an array of strings, find the longest common prefix length between adjacent strings after removals at each index.

Problem Statement

You are given an array of strings, words. For each index i in the range [0, words.length - 1], you need to perform the following steps. Remove the word at index i, and then calculate the longest common prefix (LCP) between each adjacent pair of remaining words. Return an array, answer, where answer[i] contains the length of the longest common prefix between adjacent words 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.

For example, given words = ["jump","run","run","jump","run"], you are tasked with removing each word and determining the longest common prefix of adjacent words after removal. The output for this example would be [3,0,0,3,3] as the LCP lengths between adjacent pairs after removals are computed.

Examples

Example 1

Input: words = ["jump","run","run","jump","run"]

Output: [3,0,0,3,3]

Example 2

Input: words = ["dog","racer","car"]

Output: [0,0,0]

Constraints

1 <= words.length <= 105
1 <= words[i].length <= 104
words[i] consists of lowercase English letters.
The sum of words[i].length is smaller than or equal 105.

Solution Approach

Precompute Prefixes

Precompute the longest common prefix (LCP) between adjacent pairs of strings in the array. This avoids recalculating the LCP multiple times during the removal process. Store these values in an array to quickly access them for each removal.

Efficient Removal Processing

Instead of recalculating the entire LCP after every removal, leverage the precomputed values. For each word removal, adjust the LCP of adjacent pairs and use the precomputed values to generate the correct answer array efficiently.

Edge Case Handling

Handle edge cases where removing a word might leave no adjacent pairs or where no common prefix exists. These cases should directly result in a prefix length of 0, which simplifies the implementation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity of the solution depend on the final approach. Precomputing the longest common prefix for adjacent pairs takes linear time relative to the size of the array, and processing each removal can be done in constant time by using the precomputed values. The overall complexity should be linear in terms of the number of words and their length, assuming efficient handling of string comparisons.

What Interviewers Usually Probe

Look for the ability to optimize prefix calculation by reducing redundant work.
Evaluate how well the candidate handles edge cases, such as removing a word with no adjacent pairs.
Assess the ability to articulate how precomputing adjacent pair prefixes improves efficiency.

Common Pitfalls or Variants

Common pitfalls

Failing to optimize the solution by recalculating the prefix for every removal, leading to excessive time complexity.
Not properly handling edge cases like when there are no adjacent pairs or when the LCP is zero.
Overcomplicating the problem by using nested loops instead of leveraging the precomputed values for adjacent pairs.

Follow-up variants

Modify the problem to handle case-insensitive strings.
Introduce constraints where only a certain number of removals are allowed and calculate the LCP only for those removals.
Extend the problem to handle words that have varying lengths and require dynamic adjustments to the prefix calculations.

FAQ

What is the primary approach to solve the problem "Longest Common Prefix Between Adjacent Strings After Removals"?

The key to solving this problem is to precompute the longest common prefix (LCP) between adjacent strings, and then use this precomputed data when removing each word to avoid redundant calculations.

How do I handle edge cases in the "Longest Common Prefix Between Adjacent Strings After Removals" problem?

Edge cases include situations where no adjacent pairs remain after a word is removed, or when no common prefix exists. In these cases, the result should be 0 for the corresponding index.

What data structure should I use for storing the LCP values for adjacent pairs?

An array can be used to store the LCP values for adjacent pairs, allowing you to access them in constant time during the removal process.

What is the time complexity of the solution for "Longest Common Prefix Between Adjacent Strings After Removals"?

The time complexity is linear in the size of the array, assuming the LCP for adjacent pairs is precomputed, as each removal only requires constant time for lookup.

How does precomputing the LCP values improve the solution?

Precomputing the LCP values reduces the need for repeated string comparisons, making the solution much more efficient when processing each removal.

terminal

Solution

Solution 1: Ordered Set

We define a function $\textit{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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def longestCommonPrefix(self, words: List[str]) -> List[int]:
        @cache
        def calc(s: str, t: str) -> int:
            k = 0
            for a, b in zip(s, t):
                if a != b:
                    break
                k += 1
            return k

        def add(i: int, j: int):
            if 0 <= i < n and 0 <= j < n:
                sl.add(calc(words[i], words[j]))

        def remove(i: int, j: int):
            if 0 <= i < n and 0 <= j < n:
                sl.remove(calc(words[i], words[j]))

        n = len(words)
        sl = SortedList(calc(a, b) for a, b in pairwise(words))
        ans = []
        for i in range(n):
            remove(i, i + 1)
            remove(i - 1, i)
            add(i - 1, i + 1)
            ans.append(sl[-1] if sl and sl[-1] > 0 else 0)
            remove(i - 1, i + 1)
            add(i - 1, i)
            add(i, i + 1)
        return ans

Continue Practicing

#3606 coupon code validator #3529 count cells in overlapping horizontal and vertical substrings #3527 find the most common response