LeetCode 2135: Count Words Obtained After Adding a Letter Solution

Master LeetCode problem 2135 (Count Words Obtained After Adding a Letter), a medium 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.

2135. Count Words Obtained After Adding a Letter

Medium

Array Hash Table String Bit Manipulation Sorting

Problem Explanation

Explanation:

To solve this problem, we iterate over each string in targetWords and check if we can obtain it by adding a letter from a string in startWords and rearranging the letters. We can achieve this by counting the frequency of letters in each string and then comparing if the target string can be formed by adding a missing letter and rearranging the characters.

Create a helper function to count the frequency of letters in a string.
Iterate over each string in targetWords.
For each target string, iterate over each string in startWords.
Check if the target string can be formed by adding a missing letter and rearranging the characters from the current start string.
Increment the count if a valid transformation is possible.

Time Complexity:

Let n be the length of targetWords and m be the length of startWords.
Calculating frequency of letters in a string: O(m)
Checking if a target string can be formed from a start string: O(26) = O(1)
Total time complexity: O(n * m)

Space Complexity:

Frequency count for each string: O(26) = O(1)
Total space complexity: O(1)

Solution Code

class Solution {
    public int countWordsObtainedAfterAddingALetter(String[] startWords, String[] targetWords) {
        int count = 0;
        
        for (String target : targetWords) {
            for (String start : startWords) {
                if (isTransformPossible(start, target)) {
                    count++;
                    break;
                }
            }
        }
        
        return count;
    }
    
    private boolean isTransformPossible(String start, String target) {
        if (start.length() != target.length() - 1) {
            return false;
        }
        
        int[] startFreq = new int[26];
        int[] targetFreq = new int[26];
        
        for (char c : start.toCharArray()) {
            startFreq[c - 'a']++;
        }
        
        for (char c : target.toCharArray()) {
            targetFreq[c - 'a']++;
        }
        
        for (int i = 0; i < 26; i++) {
            if (targetFreq[i] > startFreq[i]) {
                return false;
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2135 (Count Words Obtained After Adding a Letter)?

This page provides optimized solutions for LeetCode problem 2135 (Count Words Obtained After Adding a Letter) 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 2135 (Count Words Obtained After Adding a Letter)?

The time complexity for LeetCode 2135 (Count Words Obtained After Adding a Letter) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2135 on DevExCode?

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

Back to LeetCode Solutions