3598. Longest Common Prefix Between Adjacent Strings After Removals

Problem Link

Description

---

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 i from the words array.
• 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:
  • words becomes ["run", "run", "jump", "run"]
  • Longest adjacent pair is ["run", "run"] having a common prefix "run" (length 3)
• Removing index 1:
  • words becomes ["jump", "run", "jump", "run"]
  • No adjacent pairs share a common prefix (length 0)
• Removing index 2:
  • words becomes ["jump", "run", "jump", "run"]
  • No adjacent pairs share a common prefix (length 0)
• Removing index 3:
  • words becomes ["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)

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 <= 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

---

Python3

class Solution:
    def longestCommonPrefix(self, words: List[str]) -> List[int]:
        N = len(words)
 
        if N == 1: return [0]
        if N == 2: return [0, 0]
 
        def countPrefix(word1, word2):
            count = 0
 
            for a, b in zip(word1, word2):
                if a == b:
                    count += 1
                else:
                    break
            
            return count
 
        A = [0] * N
        for i in range(N - 1):
            A[i] = countPrefix(words[i], words[i + 1])
 
        prefix = [0] * N
        prefix[0] = A[0]
        for i in range(1, N):
            prefix[i] = max(prefix[i - 1], A[i])
        
        suffix = [0] * N
        suffix[-1] = A[-1]
        for i in range(N - 2, -1, -1):
            suffix[i] = max(suffix[i + 1], A[i])
            
        res = []
 
        for i in range(N):
            if i == 0:
                res.append(suffix[i + 1])
            elif i == N - 1:
                res.append(prefix[i - 2])
            else:
                curr = suffix[i + 1]
 
                if i >= 2:
                    curr = max(curr, prefix[i - 2])
 
                curr = max(curr, countPrefix(words[i - 1], words[i + 1]))
 
                res.append(curr)
        
        return res