Leetcode problem: 884. Uncommon Words from Two Sentences

Description:

A sentence is a string of single-space separated words where each word consists only of lowercase letters.

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Given two sentences s1 and s2, return a list of all the uncommon words. You may return the answer in any order.

Example 1:

Input: s1 = “this apple is sweet”, s2 = “this apple is sour”

Output: [“sweet”,”sour”]

Explanation:

The word "sweet" appears only in s1, while the word "sour" appears only in s2.

Example 2:

Input: s1 = “apple apple”, s2 = “banana”

Output: [“banana”]

Constraints:

• 1 <= s1.length, s2.length <= 200
• s1 and s2 consist of lowercase English letters and spaces.
• s1 and s2 do not have leading or trailing spaces.
• All the words in s1 and s2 are separated by a single space.

Solution:

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        
        String[] str1 = s1.split(" ");
        String[] str2 = s2.split(" ");
        int len1=str1.length;
        int len2=str2.length;
        int start1=0;
        int start2=0;
        List<String> list= new ArrayList<>();
        HashMap<String,Integer> map1 =  new HashMap<>();
        HashMap<String,Integer> map2 =  new HashMap<>();

        for(String str:str1){
            map1.put(str,map1.getOrDefault(str,0)+1);
        }

        for(String str:str2){
            map2.put(str,map2.getOrDefault(str,0)+1);
        }

        for(Map.Entry<String,Integer> set:map1.entrySet()){
            if(set.getValue() == 1 && !map2.containsKey(set.getKey())){
                list.add(set.getKey());
            }
        }

        for(Map.Entry<String,Integer> set:map2.entrySet()){
            if(set.getValue() == 1 && !map1.containsKey(set.getKey())){
                list.add(set.getKey());
            }
        }

        int size= list.size();
        String[] strnew = new String[size];
        int count= 0;

        for(int i=0;i<size;i++){
              strnew[count++] = list.get(i);
        }
      return strnew;
    }
}

Explanation:

1. Split both sentences into words: String[] str1 = s1.split(" "); String[] str2 = s2.split(" ");
2. Count frequency of each word in both sentences separately:
3. HashMap<String, Integer> map1 = new HashMap<>(); HashMap<String, Integer> map2 = new HashMap<>(); for (String str : str1) { map1.put(str, map1.getOrDefault(str, 0) + 1); } for (String str : str2) { map2.put(str, map2.getOrDefault(str, 0) + 1); }
4. Find words that occur exactly once in one sentence and not at all in the other: for (Map.Entry<String, Integer> set : map1.entrySet()) { if (set.getValue() == 1 && !map2.containsKey(set.getKey())) { list.add(set.getKey()); } } for (Map.Entry<String, Integer> set : map2.entrySet()) { if (set.getValue() == 1 && !map1.containsKey(set.getKey())) { list.add(set.getKey()); } }
5. Convert the list to an array and return it.

✅ Complexity Analysis

• Time complexity: O(n + m)
  where n and m are the number of words in s1 and s2.
• Space complexity: O(n + m)
  due to storage in HashMaps and the result list.