// Group Anagrams - https://leetcode.com/problems/group-anagrams/

class Solution {

    // Using HashMap to build dictionary
    // Time Complexity: O(n * klogk)
    //  where k is the length of string
    // Space Complexity: O(n * k)

    // Key Clarifications
    // - Do we need special handling for empty strings
    // - Can we assume that input strings are all lowercase
    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> map = new HashMap<>();

        for(int i = 0; i < strs.length; i++) {
            char[] charArray = strs[i].toCharArray();
            Arrays.sort(charArray);
            String sorted = new String(charArray);

            List<String> anagrams = map.getOrDefault(sorted, new ArrayList<>());
            anagrams.add(strs[i]);
            map.put(sorted, anagrams);
        }

        List<List<String>> result = new ArrayList<>();
        for(List<String> anagrams: map.values()) {
            result.add(anagrams);
        }

        return result;
    }
}