3485: Longest Common Prefix of K Strings After Removal
Problem Statement
You are given an array of strings words and an integer k.
For each index i in the range [0, words.length - 1], find the length of the longest common prefix among any k strings (selected at distinct indices) from the remaining array after removing the ith element.
Return an array answer, where answer[i] is the answer for ith element. If removing the ith element leaves the array with fewer than k strings, answer[i] is 0.
Example 1:
Input: words = ["jump","run","run","jump","run"], k = 2
Output: [3,4,4,3,4]
Explanation:
- Removing index 0 (
"jump"):
<ul>
<li><code>words</code> becomes: <code>["run", "run", "jump", "run"]</code>. <code>"run"</code> occurs 3 times. Choosing any two gives the longest common prefix <code>"run"</code> (length 3).</li>
</ul>
</li>
<li>Removing index 1 (<code>"run"</code>):
<ul>
<li><code>words</code> becomes: <code>["jump", "run", "jump", "run"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
</ul>
</li>
<li>Removing index 2 (<code>"run"</code>):
<ul>
<li><code>words</code> becomes: <code>["jump", "run", "jump", "run"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
</ul>
</li>
<li>Removing index 3 (<code>"jump"</code>):
<ul>
<li><code>words</code> becomes: <code>["jump", "run", "run", "run"]</code>. <code>"run"</code> occurs 3 times. Choosing any two gives the longest common prefix <code>"run"</code> (length 3).</li>
</ul>
</li>
<li>Removing index 4 ("run"):
<ul>
<li><code>words</code> becomes: <code>["jump", "run", "run", "jump"]</code>. <code>"jump"</code> occurs twice. Choosing these two gives the longest common prefix <code>"jump"</code> (length 4).</li>
</ul>
</li>
Example 2:
Input: words = ["dog","racer","car"], k = 2
Output: [0,0,0]
Explanation:
- Removing any index results in an answer of 0.
Constraints:
1 <= k <= words.length <= 1051 <= words[i].length <= 104words[i]consists of lowercase English letters.- The sum of
words[i].lengthis smaller than or equal105.
Code Solution