Count Common Words With One Occurrence
EasyPrompt
Given two string arrays words1 and words2, return the number of strings that appear exactly once in each of the two arrays.
Example 1:
Input: words1 = ["leetcode","is","amazing","as","is"], words2 = ["amazing","leetcode","is"]
Output: 2
Explanation:
- "leetcode" appears exactly once in each of the two arrays. We count this string.
- "amazing" appears exactly once in each of the two arrays. We count this string.
- "is" appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
- "as" appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.Example 2:
Input: words1 = ["b","bb","bbb"], words2 = ["a","aa","aaa"]
Output: 0
Explanation: There are no strings that appear in each of the two arrays.Example 3:
Input: words1 = ["a","ab"], words2 = ["a","a","a","ab"]
Output: 1
Explanation: The only string that appears exactly once in each of the two arrays is "ab".
Constraints:
1 <= words1.length, words2.length <= 10001 <= words1[i].length, words2[j].length <= 30words1[i]andwords2[j]consists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through each unique word in the first array, words1. For each word, it then performs two separate counts: one to find its frequency within words1 and another to find its frequency within words2. If both frequencies are exactly one, a counter is incremented. To avoid redundant checks for duplicate words within words1, a HashSet is used to keep track of words that have already been processed.
Algorithm
- Initialize a counter
commonCountto 0. - Create a
HashSetcalledprocessedto store words fromwords1that have already been checked to avoid redundant work. - Loop through each
wordinwords1:- If
wordis already inprocessed, skip to the next iteration. - Add
wordto theprocessedset. - Initialize
count1 = 0to count the frequency ofwordinwords1. - Loop through
words1again to count occurrences ofwordand updatecount1. - If
count1is exactly 1, then proceed to check inwords2. - Initialize
count2 = 0to count the frequency ofwordinwords2. - Loop through
words2to count occurrences ofwordand updatecount2. - If
count2is also exactly 1, it means the word appears once in both arrays. IncrementcommonCount.
- If
- After the loops complete, return
commonCount.
Walkthrough
The brute-force method directly translates the problem's conditions into nested loops. We iterate through each word in the first list, words1. To ensure we only consider each unique word once, we use a Set to keep track of words we've already analyzed. For a given word, we first count its occurrences in words1. If the count isn't one, we move on. If it is one, we then proceed to count its occurrences in words2. If that count is also one, we've found a word that satisfies the condition, and we increment our result counter.
import java.util.HashSet;import java.util.Set; class Solution { public int countWords(String[] words1, String[] words2) { int commonCount = 0; Set<String> processed = new HashSet<>(); for (String word1 : words1) { if (processed.contains(word1)) { continue; } processed.add(word1); int count1 = 0; for (String w : words1) { if (w.equals(word1)) { count1++; } } if (count1 == 1) { int count2 = 0; for (String w : words2) { if (w.equals(word1)) { count2++; } } if (count2 == 1) { commonCount++; } } } return commonCount; }}Complexity
Time
O(N * (N*L + M*L)), where N is the length of `words1`, M is the length of `words2`, and L is the maximum length of a word. For each of the (at most) N unique words in `words1`, we iterate through `words1` (cost `N*L`) and `words2` (cost `M*L`). This quadratic complexity makes it very slow for larger inputs.
Space
O(U * L), where U is the number of unique words in `words1` and L is the maximum length of a word. This space is used by the `processed` set. In the worst case, U can be N (the total number of words in `words1`), making the space complexity O(N * L).
Trade-offs
Pros
Simple to understand and implement without requiring knowledge of more complex data structures.
Uses a relatively small amount of extra space if the number of unique words is low.
Cons
Extremely inefficient due to nested loops, leading to a high time complexity.
Performs redundant computations by repeatedly scanning the arrays.
Likely to result in a 'Time Limit Exceeded' error on larger test cases.
Solutions
Solution
class Solution {public int countWords(String[] words1, String[] words2) { Map<String, Integer> cnt1 = new HashMap<>(); Map<String, Integer> cnt2 = new HashMap<>(); for (var w : words1) { cnt1.merge(w, 1, Integer : : sum); } for (var w : words2) { cnt2.merge(w, 1, Integer : : sum); } int ans = 0; for (var e : cnt1.entrySet()) { if (e.getValue() == 1 && cnt2.getOrDefault(e.getKey(), 0) == 1) { ++ans; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.