LeetCode 3485: Longest Common Prefix of K Strings After Removal Solution

Master LeetCode problem 3485 (Longest Common Prefix of K Strings After Removal), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3485. Longest Common Prefix of K Strings After Removal

Hard

Array String Trie

Problem Explanation

Explanation

To solve this problem, we can iterate over each word in the input array and remove that word. Then we find the longest common prefix among any k strings from the remaining array. We repeat this process for each word and store the lengths of the longest common prefixes in the answer array. If after removing a word, there are fewer than k strings remaining, we set the answer for that index to 0.

Create an answer array of the same size as the input array.
Iterate over each word in the input array.
Remove the current word from the array and find the longest common prefix among any k strings from the remaining array.
Store the length of the longest common prefix in the answer array.
If after removing a word, there are fewer than k strings remaining, set the answer for that index to 0.
Return the answer array.

Time Complexity: O(n * m * k) where n is the number of words, m is the average length of a word, and k is the given k value. Space Complexity: O(n) where n is the number of words in the input array.

Solution Code

class Solution {
    public int[] longestCommonPrefix(String[] words, int k) {
        int n = words.length;
        int[] answer = new int[n];
        
        for (int i = 0; i < n; i++) {
            List<String> remaining = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    remaining.add(words[j]);
                }
            }
            int maxLen = 0;
            for (int j = 0; j < remaining.size(); j++) {
                int commonLen = longestCommonPrefixLength(remaining, k, j);
                maxLen = Math.max(maxLen, commonLen);
            }
            answer[i] = maxLen;
        }
        
        return answer;
    }
    
    private int longestCommonPrefixLength(List<String> words, int k, int idx) {
        int count = 0;
        String first = words.get(idx);
        for (String word : words) {
            if (word.equals(first) || commonPrefixLength(word, first) >= k) {
                count++;
            }
        }
        return count == words.size() ? first.length() : 0;
    }
    
    private int commonPrefixLength(String word1, String word2) {
        int len = 0;
        for (int i = 0; i < Math.min(word1.length(), word2.length()); i++) {
            if (word1.charAt(i) == word2.charAt(i)) {
                len++;
            } else {
                break;
            }
        }
        return len;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3485 (Longest Common Prefix of K Strings After Removal)?

This page provides optimized solutions for LeetCode problem 3485 (Longest Common Prefix of K Strings After Removal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3485 (Longest Common Prefix of K Strings After Removal)?

The time complexity for LeetCode 3485 (Longest Common Prefix of K Strings After Removal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3485 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3485 in Java, C++, or Python.

Back to LeetCode Solutions