3485. Longest Common Prefix of K Strings After Removal LeetCode Solution
In this guide, you will get 3485. Longest Common Prefix of K Strings After Removal LeetCode Solution with the best time and space complexity. The solution to Longest Common Prefix of K Strings After Removal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Longest Common Prefix of K Strings After Removal solution in C++
- Longest Common Prefix of K Strings After Removal solution in Java
- Longest Common Prefix of K Strings After Removal solution in Python
- Additional Resources
Problem Statement of Longest Common Prefix of K Strings After Removal
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”):
words becomes: [“run”, “run”, “jump”, “run”]. “run” occurs 3 times. Choosing any two gives the longest common prefix “run” (length 3).
Removing index 1 (“run”):
words becomes: [“jump”, “run”, “jump”, “run”]. “jump” occurs twice. Choosing these two gives the longest common prefix “jump” (length 4).
Removing index 2 (“run”):
words becomes: [“jump”, “run”, “jump”, “run”]. “jump” occurs twice. Choosing these two gives the longest common prefix “jump” (length 4).
Removing index 3 (“jump”):
words becomes: [“jump”, “run”, “run”, “run”]. “run” occurs 3 times. Choosing any two gives the longest common prefix “run” (length 3).
Removing index 4 (“run”):
words becomes: [“jump”, “run”, “run”, “jump”]. “jump” occurs twice. Choosing these two gives the longest common prefix “jump” (length 4).
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 <= 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.
Complexity Analysis
- Time Complexity: O(\Sigma |\texttt{words[i]}|)
- Space Complexity: O(\Sigma |\texttt{words[i]}|)
3485. Longest Common Prefix of K Strings After Removal LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
int count = 0;
TrieNode() : children(26) {}
};
class Trie {
public:
Trie(int k) : k(k) {}
void insert(const string& word) {
shared_ptr<TrieNode> node = root;
for (int i = 0; i < word.length(); ++i) {
const int sz = i + 1;
const int index = word[i] - 'a';
if (node->children[index] == nullptr)
node->children[index] = make_shared<TrieNode>();
node = node->children[index];
++node->count;
if (node->count >= k && prefixLengthsCount[sz]++ == 0)
prefixLengths.insert(sz);
}
}
void erase(const string& word) {
shared_ptr<TrieNode> node = root;
for (int i = 0; i < word.length(); ++i) {
const int sz = i + 1;
const int index = word[i] - 'a';
if (node->children[index] == nullptr)
node->children[index] = make_shared<TrieNode>();
node = node->children[index];
if (node->count == k && prefixLengthsCount[sz]-- == 1)
prefixLengths.erase(sz);
--node->count;
}
}
int getLongestCommonPrefix() const {
return prefixLengths.empty() ? 0 : *prefixLengths.begin();
}
private:
const int k;
shared_ptr<TrieNode> root = make_shared<TrieNode>();
unordered_map<int, int> prefixLengthsCount;
set<int, greater<>> prefixLengths;
};
class Solution {
public:
vector<int> longestCommonPrefix(vector<string>& words, int k) {
vector<int> ans;
Trie trie(k);
for (const string& word : words)
trie.insert(word);
for (const string& word : words) {
trie.erase(word);
ans.push_back(trie.getLongestCommonPrefix());
trie.insert(word);
}
return ans;
}
};
/* code provided by PROGIEZ */3485. Longest Common Prefix of K Strings After Removal LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public int count = 0;
}
class Trie {
public Trie(int k) {
this.k = k;
}
public void insert(final String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); ++i) {
final int sz = i + 1;
final int index = word.charAt(i) - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();
node = node.children[index];
++node.count;
if (node.count >= k && prefixLengthsCount.merge(sz, 1, Integer::sum) == 1)
prefixLengths.add(sz);
}
}
public void erase(final String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); ++i) {
final int sz = i + 1;
final int index = word.charAt(i) - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();
node = node.children[index];
if (node.count == k && prefixLengthsCount.merge(sz, -1, Integer::sum) == 0)
prefixLengths.remove(sz);
--node.count;
}
}
public int getLongestCommonPrefix() {
return prefixLengths.isEmpty() ? 0 : prefixLengths.first();
}
private final int k;
private TrieNode root = new TrieNode();
private Map<Integer, Integer> prefixLengthsCount = new HashMap<>();
private TreeSet<Integer> prefixLengths = new TreeSet<>(Collections.reverseOrder());
}
class Solution {
public int[] longestCommonPrefix(String[] words, int k) {
final int[] ans = new int[words.length];
Trie trie = new Trie(k);
for (final String word : words)
trie.insert(word);
for (int i = 0; i < words.length; ++i) {
trie.erase(words[i]);
ans[i] = trie.getLongestCommonPrefix();
trie.insert(words[i]);
}
return ans;
}
}
// code provided by PROGIEZ3485. Longest Common Prefix of K Strings After Removal LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: dict[str, TrieNode] = {}
self.count = 0
class Trie:
def __init__(self, k: int):
self.k = k
self.root = TrieNode()
self.prefixLengthsCount = collections.Counter()
self.prefixLengths = SortedList()
def insert(self, word: str) -> None:
node = self.root
for i, c in enumerate(word):
sz = i + 1
node = node.children.setdefault(c, TrieNode())
node.count += 1
if node.count >= self.k:
self.prefixLengthsCount[sz] += 1
if self.prefixLengthsCount[sz] == 1:
self.prefixLengths.add(-sz)
def erase(self, word: str) -> None:
node = self.root
for i, c in enumerate(word):
sz = i + 1
node = node.children[c]
if node.count == self.k:
self.prefixLengthsCount[sz] -= 1
if self.prefixLengthsCount[sz] == 0:
self.prefixLengths.remove(-sz)
node.count -= 1
def getLongestCommonPrefix(self) -> int:
return 0 if not self.prefixLengths else -self.prefixLengths[0]
class Solution:
def longestCommonPrefix(self, words: list[str], k: int) -> list[int]:
ans = []
trie = Trie(k)
for word in words:
trie.insert(word)
for word in words:
trie.erase(word)
ans.append(trie.getLongestCommonPrefix())
trie.insert(word)
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.