[Neetcode] Group Anagrams

https://neetcode.io/problems/anagram-groups?list=neetcode150

initial

in py we can just use counter but im using java so i will convert each word to a hashamp of character and its freq and make this a string form of key for my hashamp. if we havent this word, maybe ill store this word in a list that is hashamps value and for key its the string format of the key?

yes it works but more simply, u can just sort each string and make that as a key

some things i didnt know:
1) sorting string: we have to convert toCharArray(), sort and make it to string via new String()
2) computeIfAbsent(key, k->new ArrayList<>()) makes value for the missing key

sol

import collections

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        # Use a defaultdict for cleaner code.
        # It automatically creates a new list for a key if it doesn't exist.
        anagram_map = collections.defaultdict(list)
        
        for word in strs:
            # Sort the characters to create a canonical key.
            # Convert the sorted list of characters back to a string.
            sorted_word = "".join(sorted(word))
            
            # Use the sorted word as the key and append the original word to its list.
            anagram_map[sorted_word].append(word)
        
        # Return the values (the lists of anagrams) from the dictionary.
        return list(anagram_map.values())

if we wanna sort by length of val, we pass len as the key parameter when sorting

from collections import defaultdict
from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 1. Group Anagrams (Same as yours, optimal)
        anagram_groups = defaultdict(list)
        for word in strs:
            key = ''.join(sorted(word))
            anagram_groups[key].append(word)

        # 2. Extract Values and Sort (More concise)
        # We get all the values (the lists of anagrams) from the dictionary.
        # Then, we sort this list of lists by the length of each inner list.
        return sorted(anagram_groups.values(), key=len)

java

as mentioned, if i do

            map.getOrDefault(new_string, new ArrayList<>()).add(s);

this adds string s to the list but it doesnt save it to dictionary. We thus get an empty dictionary cuz its not updated. We need to use computeIfAbsent, which checks if key exists and if not, creates the value, puts it in the map.

map.computeIfAbsent(new_string, k -> new ArrayList<>()).add(s);

## is same as 
if (!map.containsKey(new_string)) {
    map.put(new_string, new ArrayList<>());
}
map.get(new_string).add(s);

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s:strs){
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String new_string = new String(arr);
            
            map.computeIfAbsent(new_string, k-> new ArrayList<>()).add(s);
        }
        List<List<String>> ans = new ArrayList<>();
        for(Map.Entry<String,List<String>> entry: map.entrySet()){
            ans.add(entry.getValue());
        }
        return ans;
    }
}

complexity

each word so thats n and we are sorting so is n log n nested inside that n so n^2 log n time?

not exaclty, lets say max length of string word is k so its k log k for sorting. So total time is n* k log k.

n space