3598. Longest Common Prefix Between Adjacent Strings After Removals

MediumArrayString

Problem 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve the problem efficiently, notice that removing a string at position i only affects the pairs that are directly adjacent to it. All other pairs in the array remain unchanged. Before any removal, the longest common prefix is calculated for every pair of adjacent words. When a word at index i is removed, the pairs (i-1, i) and (i, i+1) are broken, and a new pair (i-1, i+1) might be formed if both exist. So, we can update the set of prefix lengths by removing the affected pairs and adding the potential new pair, instead of recalculating everything. This helps answer each query efficiently with minimal work for each removal, by just updating where changes happen.

Solution Approach

The solution uses an ordered set (such as a balanced BST or a SortedList) to efficiently maintain and update the lengths of longest common prefixes between adjacent word pairs as we process removals.

First, a helper function calc(s, t) computes the longest common prefix length between two strings s and t. For every original adjacent pair (a, b) in words, calc(a, b) is calculated and added to the ordered set.

For each index i (where the word at position i is removed), the updates are localized:

Remove the prefix length for the pair (i-1, i) if it exists.
Remove the prefix length for the pair (i, i+1) if it exists.
If both neighbors exist, add the prefix length for the new adjacent pair (i-1, i+1), which only appears after removing words[i].

After these updates, the maximum value in the ordered set represents the length of the longest common prefix for any existing adjacent pair after removal. This value is saved to the answer for position i. If the set is empty or all values are zero, 0 is saved.

Finally, to restore the state before moving to the next removal, revert the changes by:

Removing the new pair (i-1, i+1) (if it was added).
Re-adding the original pairs (i-1, i) and (i, i+1) (if they existed).

By focusing only on the affected positions and using a data structure that allows for efficient insertions, deletions, and maximum queries, the overall process remains fast compared to recalculating every pair for each removal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the example: words = ["apple", "apex", "apron"]

Step 1: Preprocessing

Compute the longest common prefix for each adjacent pair:
- Pair (0,1): "apple" vs "apex" → Prefix: "ap" (Length 2)
- Pair (1,2): "apex" vs "apron" → Prefix: "ap" (Length 2)
Store these prefix lengths: [2, 2] (positions refer to pairs: (0,1) and (1,2))

Step 2: Process each removal

Remove index 0 ("apple"):

Remove prefix for pair (0,1): Remove 2 from the set.
There's no left neighbor, so no new pair formed.
Only pair left is (1,2): Prefix length 2.
Maximum prefix length is 2.
Restore the set for next operation.

Remove index 1 ("apex"):

Remove prefix for pairs (0,1) and (1,2): Remove both 2’s.
Add prefix for new pair (0,2): "apple" vs "apron" → Prefix: "ap" (Length 2).
Set contains [2].
Maximum prefix length is 2.
Restore the set for next operation.

Remove index 2 ("apron"):

Only need to remove prefix for pair (1,2): Remove 2.
Only pair left is (0,1): Prefix length 2.
Maximum prefix length is 2.
Restore the set for next operation.

So, the final answer is: [2, 2, 2]

This process demonstrates how, by updating and maintaining only the affected adjacent pairs using an ordered set, the solution efficiently calculates the answer for each removal without redundant recalculations.

Solution Implementation

1from typing import List
2from functools import cache
3from itertools import pairwise
4from sortedcontainers import SortedList
5
6class Solution:
7    def longestCommonPrefix(self, words: List[str]) -> List[int]:
8        # Memoization: computes the common prefix length between two words
9        @cache
10        def calc_prefix_length(word1: str, word2: str) -> int:
11            prefix_length = 0
12            for char1, char2 in zip(word1, word2):
13                if char1 != char2:
14                    break
15                prefix_length += 1
16            return prefix_length
17
18        # Insert the prefix length of words[i] and words[j] into the sorted list (if valid indices)
19        def add_pair(i: int, j: int):
20            if 0 <= i < num_words and 0 <= j < num_words:
21                sorted_prefixes.add(calc_prefix_length(words[i], words[j]))
22
23        # Remove the prefix length of words[i] and words[j] from the sorted list (if valid indices)
24        def remove_pair(i: int, j: int):
25            if 0 <= i < num_words and 0 <= j < num_words:
26                sorted_prefixes.remove(calc_prefix_length(words[i], words[j]))
27
28        num_words = len(words)
29
30        # Initialize sorted list with the prefix lengths of all adjacent word pairs
31        sorted_prefixes = SortedList(calc_prefix_length(a, b) for a, b in pairwise(words))
32        result = []
33
34        # For each index, "remove" the word at that index and compute the new max prefix
35        for i in range(num_words):
36            remove_pair(i, i + 1)
37            remove_pair(i - 1, i)
38            add_pair(i - 1, i + 1)
39
40            # If the sorted list is not empty, take the maximum (end of list), else 0
41            result.append(sorted_prefixes[-1] if sorted_prefixes and sorted_prefixes[-1] > 0 else 0)
42
43            # Revert the simulated removals/additions for the next iteration
44            remove_pair(i - 1, i + 1)
45            add_pair(i - 1, i)
46            add_pair(i, i + 1)
47
48        return result
49

1import java.util.TreeMap;
2
3class Solution {
4    // TreeMap to maintain the frequencies of prefix lengths
5    private final TreeMap<Integer, Integer> prefixCount = new TreeMap<>();
6    // Array to store the input words
7    private String[] wordsArray;
8    // Number of words
9    private int length;
10
11    public int[] longestCommonPrefix(String[] words) {
12        length = words.length;
13        wordsArray = words;
14
15        // Initialize the map with the prefix lengths between adjacent words
16        for (int i = 0; i + 1 < length; ++i) {
17            int commonPrefix = calc(wordsArray[i], wordsArray[i + 1]);
18            prefixCount.merge(commonPrefix, 1, Integer::sum);
19        }
20
21        int[] result = new int[length];
22
23        for (int i = 0; i < length; ++i) {
24            // Remove impact of i and adjacent from the map
25            remove(i, i + 1);
26            remove(i - 1, i);
27            // Add combined interval of previous and next (skipping current)
28            add(i - 1, i + 1);
29
30            // If the map is not empty and largest key is positive,
31            // set result[i], else set to 0
32            result[i] = (!prefixCount.isEmpty() && prefixCount.lastKey() > 0) ? prefixCount.lastKey() : 0;
33
34            // Revert the changes to restore TreeMap for next iteration
35            remove(i - 1, i + 1);
36            add(i - 1, i);
37            add(i, i + 1);
38        }
39        return result;
40    }
41
42    // Adds the prefix length of words at index i and j into the map
43    private void add(int i, int j) {
44        if (isValidIndex(i) && isValidIndex(j)) {
45            int commonPrefix = calc(wordsArray[i], wordsArray[j]);
46            prefixCount.merge(commonPrefix, 1, Integer::sum);
47        }
48    }
49
50    // Removes the prefix length of words at index i and j from the map
51    private void remove(int i, int j) {
52        if (isValidIndex(i) && isValidIndex(j)) {
53            int commonPrefix = calc(wordsArray[i], wordsArray[j]);
54            int count = prefixCount.merge(commonPrefix, -1, Integer::sum);
55            if (count == 0) {
56                prefixCount.remove(commonPrefix);
57            }
58        }
59    }
60
61    // Returns length of the longest common prefix for two given words
62    private int calc(String s, String t) {
63        int minLength = Math.min(s.length(), t.length());
64        for (int k = 0; k < minLength; ++k) {
65            if (s.charAt(k) != t.charAt(k)) {
66                return k;
67            }
68        }
69        return minLength;
70    }
71
72    // Utility method to check if index is within the bounds of wordsArray
73    private boolean isValidIndex(int idx) {
74        return idx >= 0 && idx < length;
75    }
76}
77

1#include <vector>
2#include <string>
3#include <set>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10    // Main function to return the array of longest common prefixes after removing each word
11    vector<int> longestCommonPrefix(vector<string>& words) {
12        int n = words.size();
13
14        // Multiset to maintain all consecutive pairs' common prefix lengths
15        multiset<int> prefixLengths;
16
17        // Helper lambda to calculate common prefix length between two strings
18        auto calcCommonPrefix = [](const string& s, const string& t) -> int {
19            int len = min(s.size(), t.size());
20            for (int k = 0; k < len; ++k) {
21                if (s[k] != t[k])
22                    return k;
23            }
24            return len;
25        };
26
27        // Initialize prefixLengths for all adjacent word pairs
28        for (int i = 0; i + 1 < n; ++i) {
29            prefixLengths.insert(calcCommonPrefix(words[i], words[i + 1]));
30        }
31
32        vector<int> result(n);
33
34        // Helper function to add the prefix length of pair (i, j) to prefixLengths
35        auto addPrefix = [&](int i, int j) {
36            if (i >= 0 && i < n && j >= 0 && j < n) {
37                prefixLengths.insert(calcCommonPrefix(words[i], words[j]));
38            }
39        };
40
41        // Helper function to remove the prefix length of pair (i, j) from prefixLengths
42        auto removePrefix = [&](int i, int j) {
43            if (i >= 0 && i < n && j >= 0 && j < n) {
44                int val = calcCommonPrefix(words[i], words[j]);
45                auto it = prefixLengths.find(val);
46                if (it != prefixLengths.end()) {
47                    prefixLengths.erase(it);
48                }
49            }
50        };
51
52        // For each word, simulate its removal and compute the new common prefix length
53        for (int i = 0; i < n; ++i) {
54            // Remove affected pairs when removing words[i]
55            removePrefix(i, i + 1);
56            removePrefix(i - 1, i);
57
58            // Add the new pair formed by the join after removal
59            addPrefix(i - 1, i + 1);
60
61            // The current longest common prefix is the largest value in prefixLengths
62            result[i] = prefixLengths.empty() ? 0 : *prefixLengths.rbegin();
63
64            // Rollback: remove the new pair and restore the original pairs
65            removePrefix(i - 1, i + 1);
66            addPrefix(i - 1, i);
67            addPrefix(i, i + 1);
68        }
69
70        return result;
71    }
72};
73

1// Helper function: Calculates common prefix length between two strings
2function calcCommonPrefix(s: string, t: string): number {
3    const len = Math.min(s.length, t.length);
4    for (let k = 0; k < len; ++k) {
5        if (s[k] !== t[k]) return k;
6    }
7    return len;
8}
9
10// Simulates a multiset using a Map (for element count)
11class MultiSet {
12    private map: Map<number, number>;
13    private sorted: number[];
14
15    constructor() {
16        this.map = new Map<number, number>();
17        this.sorted = [];
18    }
19
20    insert(val: number) {
21        this.map.set(val, (this.map.get(val) ?? 0) + 1);
22        this.sorted.push(val);
23    }
24
25    erase(val: number) {
26        if (!this.map.has(val)) return;
27        const count = this.map.get(val)!;
28        if (count === 1) {
29            this.map.delete(val);
30            // Remove from sorted array once
31            const idx = this.sorted.indexOf(val);
32            if (idx !== -1) this.sorted.splice(idx, 1);
33        } else {
34            this.map.set(val, count - 1);
35            // Remove one occurrence from sorted array
36            const idx = this.sorted.indexOf(val);
37            if (idx !== -1) this.sorted.splice(idx, 1);
38        }
39    }
40
41    // Returns the largest value (since they represent prefix lengths)
42    getMax(): number | undefined {
43        if (this.sorted.length === 0) return undefined;
44        return Math.max(...this.sorted);
45    }
46
47    isEmpty(): boolean {
48        return this.sorted.length === 0;
49    }
50}
51
52// Main function that returns the array of longest common prefixes after removing each word
53function longestCommonPrefix(words: string[]): number[] {
54    const n = words.length;
55    const prefixLengths = new MultiSet();
56
57    // Initialize: store all adjacent pairs' common prefix lengths
58    for (let i = 0; i + 1 < n; ++i) {
59        prefixLengths.insert(calcCommonPrefix(words[i], words[i + 1]));
60    }
61
62    const result: number[] = new Array(n);
63
64    // Helper to add prefix length for pair (i, j)
65    function addPrefix(i: number, j: number) {
66        if (i >= 0 && i < n && j >= 0 && j < n) {
67            prefixLengths.insert(calcCommonPrefix(words[i], words[j]));
68        }
69    }
70
71    // Helper to remove prefix length for pair (i, j)
72    function removePrefix(i: number, j: number) {
73        if (i >= 0 && i < n && j >= 0 && j < n) {
74            const val = calcCommonPrefix(words[i], words[j]);
75            prefixLengths.erase(val);
76        }
77    }
78
79    // For each word, simulate its removal, calculate max common prefix, then rollback changes
80    for (let i = 0; i < n; ++i) {
81        // Remove affected pairs
82        removePrefix(i, i + 1);
83        removePrefix(i - 1, i);
84
85        // Add new pair formed by the join after removal
86        addPrefix(i - 1, i + 1);
87
88        // Record the current max common prefix
89        result[i] = prefixLengths.isEmpty() ? 0 : (prefixLengths.getMax() as number);
90
91        // Rollback: restore original pairs for next iteration
92        removePrefix(i - 1, i + 1);
93        addPrefix(i - 1, i);
94        addPrefix(i, i + 1);
95    }
96
97    return result;
98}
99

Time and Space Complexity

Time Complexity: The initial computation of common prefixes between adjacent pairs, using pairwise(words), takes O(L), where L is the total length of all strings. In the loop, for each of the n positions, a constant number of operations are performed on a SortedList containing at most n-1 elements, each modification (add/remove) taking O(\log n) time. Therefore, the total loop cost is O(n \log n). Combined, the total time complexity is O(L + n \log n).
Space Complexity: The SortedList stores O(n) prefix lengths. The memoization from @cache could store up to O(n^2) entries, but in practice, only adjacent or close-by pairs are used, so typical space usage is O(n). Thus, the overall space complexity is O(n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know