3598. Longest Common Prefix Between Adjacent Strings After Removals | 1655

 1class Solution:
 2    def longestCommonPrefix(self, words: List[str]) -> List[int]:
 3        # first pass  x record longest length and location(s) between i   and i+1
 4        # second pass y record longest length and location(s) between i-1 and i+1
 5
 6        #  ["jump","run","run","jump","run"]
 7        # x:  0,     3,    0,    0
 8        # y:         0,    0,    3
 9
10        #   ["hi", "hihi", "hi", "hihi", "hi", "hi"]
11        # x:  0,     0,     0,     0,     2
12        # y:         2,     4,     2,     0
13
14        # when we remove i
15        # x will be destroyed
16        # y will be established
17
18        # therefore we need to keep track of the best and the second best x
19        # if multiple bests, output is constant [max(3, y[i]), max(3, y[i]), max(3, y[i]), ...]
20        # if only one best, output is similar to [3,0,0,3,3] where 0 is the second best
21
22        # helper: given two words, return prefix length
23        def prefixLength(word_a: str, word_b: str) -> int:
24            n = min(len(word_a), len(word_b))
25            result = 0
26            while result < n and word_a[result] == word_b[result]:
27                result += 1
28            return result
29
30        words_len = len(words)
31        best_x, second_best_x = 0, 0
32        best_x_idx, second_best_x_idx = [], []
33        y = [0] * words_len
34
35        # construct x
36        for i in range(words_len - 1):
37            x = prefixLength(words[i], words[i + 1])
38            if x > best_x:
39                second_best_x = best_x
40                second_best_x_idx = best_x_idx
41                best_x = x
42                best_x_idx = [i]
43            elif x == best_x:
44                best_x_idx.append(i)
45            elif x > second_best_x:
46                second_best_x = x
47                second_best_x_idx = [i]
48            elif x == second_best_x:
49                second_best_x_idx.append(i)
50
51        # construct y
52        for i in range(1, words_len - 1):
53            y[i] = prefixLength(words[i - 1], words[i + 1])
54
55        # construct result
56        result = [0] * words_len
57
58        if not best_x:
59            for i in range(words_len):
60                y_i = y[i]
61                if y_i > 0:
62                    result[i] = y_i
63        elif len(best_x_idx) == 1:
64            for i in range(words_len):
65                if i == best_x_idx[0] or i == best_x_idx[0] + 1:
66                    result[i] = max(second_best_x, y[i])
67                else:
68                    result[i] = max(best_x, y[i])
69        else:  # lots of best_x, most straightforward
70            for i in range(words_len):
71                result[i] = max(best_x, y[i])
72
73        return result