For each index removal query, determine the maximum common prefix length among all adjacent strings in the remaining array.
Problem
You are given an array of strings words. For each query, one index is removed from the array, and the remaining strings keep their original relative order.
For the array that remains after the removal, consider every pair of adjacent strings. For each adjacent pair, compute the length of their longest common prefix (LCP). Your task is to return the maximum LCP length among all adjacent pairs in the remaining array.
If fewer than two strings remain after a removal, the answer for that query is 0.
Goal
Process all queries and report the maximum adjacent-prefix value after each removal.
Notes
- The longest common prefix of two strings is the longest string that is a prefix of both.
- Only adjacent pairs in the current array matter after each removal.
- Removing one element can only affect the pairs around that element; other adjacent pairs remain unchanged.
Input Format
- An array
wordsof strings. - A list of removal queries, where each query specifies an index in
wordsto remove.
For each query, consider the array formed by deleting that one element and keeping the rest in order.
Output Format
- Return an array of integers.
- The
i-th value is the maximum LCP length among all adjacent pairs after applying thei-th removal query.
Constraints
1 <= words.length- Each query removes exactly one valid index.
- Strings contain lowercase English letters.
- The answer for a query is
0if the remaining array has fewer than 2 strings.
Exact limits are not provided here; assume the intended solution should be efficient across many queries.
Example 1
Input
words = ["flower", "flow", "flight", "flute"], queries = [1, 2]
Output
[2, 4]
Explanation
- Remove index 1 (
"flow"): remaining words are["flower", "flight", "flute"]. Adjacent LCPs arefl= 2 andfl= 2, so the maximum is2. - Remove index 2 (
"flight"): remaining words are["flower", "flow", "flute"]. Adjacent LCPs areflowvsflower= 4 andflowvsflute= 2, so the maximum is4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.