Skip to main content
Talentd

Longest Common Prefix Between Adjacent Strings After Removals - Solution & Explanation

MediumArrayString11 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given an array of strings. After removing a string, the adjacency between remaining strings changes. The task is to determine the maximum longest common prefix (LCP) between any pair of adjacent strings after each removal.

Approach 1: Recompute Adjacent LCP After Each Removal (Brute Force) (Time: O(n2 * m), Space: O(1))

Simulate every removal and recompute the longest common prefix for all adjacent pairs in the remaining array. For each pair, iterate character by character until characters differ. If the average string length is m, each LCP calculation costs O(m), and there are up to O(n) pairs per simulation. This approach is straightforward but inefficient because the entire array is rescanned after every removal.

Approach 2: Ordered Set with Dynamic LCP Updates (Time: O(n log n + k · m), Space: O(n))

Maintain an ordered set of active indices representing the current string order. Precompute the LCP between every original adjacent pair using a helper function that scans characters until they differ. Store these values in a structure that can quickly track the maximum, such as a multiset or priority container.

When a string at index i is removed, only the neighboring relationships change. Remove the LCP values for pairs (i-1, i) and (i, i+1). Then compute a new LCP for the new adjacent pair (i-1, i+1) and insert it into the set. Because only local neighbors are affected, each update requires O(log n) ordered-set operations plus O(m) time to compute the new prefix length.

This technique avoids recomputing all adjacent pairs. The ordered structure efficiently tracks neighbors, and the multiset allows quick retrieval of the maximum LCP after each update.

The solution relies on common operations from array indexing and string prefix comparison from string problems. The ordered index maintenance resembles techniques used with balanced trees or ordered containers.

Recommended for interviews: The ordered set approach. Interviewers want to see that you recognize only local adjacency changes after a removal. Recomputing everything shows basic understanding, but maintaining neighbor relationships with an ordered structure demonstrates stronger algorithmic thinking and reduces the complexity to roughly O(n log n).

Solution

We define a function 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.

Define a function add(i, j), which adds the longest common prefix length of the string pair at indices i and j to the ordered set. Define a function remove(i, j), which removes the longest common prefix length of the string pair at indices i and j from the ordered set.

First, we compute the longest common prefix lengths for all adjacent string pairs and store them in the ordered set. Then, for each index i, we perform the following steps:

  1. Remove the longest common prefix length of the string pair at indices i and i + 1.
  2. Remove the longest common prefix length of the string pair at indices i - 1 and i.
  3. Add the longest common prefix length of the string pair at indices i - 1 and i + 1.
  4. Add the current maximum value in the ordered set (if it exists and is greater than 0) to the answer.
  5. Remove the longest common prefix length of the string pair at indices i - 1 and i + 1.
  6. Add the longest common prefix length of the string pair at indices i - 1 and i.
  7. Add the longest common prefix length of the string pair at indices i and i + 1.

In this way, after removing each string, we can quickly compute the longest common prefix length between adjacent string pairs.

The time complexity is O(L + n times log n), and the space complexity is O(n), where L is the total length of all strings and n is the number of strings.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recompute After Each Removal (Brute Force)O(n² · m)O(1)Small input sizes or quick prototype implementation
Ordered Set with Dynamic LCP TrackingO(n log n + k · m)O(n)General case where removals change adjacency and fast updates are required

Video Solution

3598. Longest Common Prefix Between Adjacent Strings After Removals | Weekly Contest 456🔥 | Java • ExpertFunda • 838 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Longest Common Prefix Between Adjacent Strings After Removals easy or hard?
The problem is rated Medium because the prefix comparison itself is simple, but efficiently handling adjacency changes after removals requires careful use of ordered sets and incremental updates.
Longest Common Prefix Between Adjacent Strings After Removals Python/Java solution
Implement an ordered structure to store active indices and maintain LCP values for adjacent pairs. On each removal, delete the affected pairs, compute the new LCP between the new neighbors, and update the container tracking the maximum. The same logic works across Python, Java, C++, and Go using language‑specific ordered collections.
How to solve Longest Common Prefix Between Adjacent Strings After Removals in O(n)?
A strict O(n) solution is generally not feasible because maintaining dynamically changing adjacency requires ordered updates. The closest practical approach uses an ordered set or balanced tree with O(log n) updates while computing only the necessary LCP values instead of recomputing all pairs.
What is the best approach for Longest Common Prefix Between Adjacent Strings After Removals?
The ordered set approach is the most efficient. Maintain active indices in a balanced ordered structure and store LCP values for adjacent pairs. When a string is removed, only neighboring pairs change, so you update at most two old pairs and add one new pair. This keeps updates around O(log n) plus the cost of computing a single prefix.
Is Longest Common Prefix Between Adjacent Strings After Removals asked at Google/Amazon/Meta?
Problems combining dynamic array updates with string prefix comparisons appear frequently in interviews at large companies like Google, Amazon, and Meta. Variants often test ordered sets, neighbor tracking, or efficient updates to pairwise relationships after deletions.
What data structure is used in Longest Common Prefix Between Adjacent Strings After Removals?
The core data structure is an ordered set (such as TreeSet in Java, set with ordering in C++, or a balanced BST). It tracks the remaining string indices so neighbors can be found quickly. A multiset or priority container is typically used to maintain the maximum LCP among adjacent pairs.
What is the time complexity of Longest Common Prefix Between Adjacent Strings After Removals?
The optimal solution runs in roughly O(n log n + k · m), where n is the number of strings, k is the number of removals, and m is the average string length used when computing a longest common prefix. Ordered set updates take O(log n), while each LCP computation costs O(m).

Ready to solve this problem?

Practice Longest Common Prefix Between Adjacent Strings After Removals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays