Group Anagrams Using Hashing — The Smart O(n·k) Solution

import java.util.Arrays;

public class AnagramKeyDemo {

    /**
     * Strategy 1: sort the characters of the word to produce a canonical key.
     * "listen" -> "eilnst",  "silent" -> "eilnst"  (same key!)
     * Time per word: O(k log k) where k = word length
     */
    public static String sortedKey(String word) {
        char[] characters = word.toLowerCase().toCharArray(); // normalise case first
        Arrays.sort(characters);                              // sort the chars alphabetically
        return new String(characters);                        // turn the sorted array back into a string key
    }

    /**
     * Strategy 2: count character frequencies and serialise the counts.
     * "listen" -> "0#0#0#0#1#0#0#0#1#0#0#1#0#1#0#0#0#0#1#1#0#0#0#0#0#0"
     * Time per word: O(k) — faster for long strings
     */
    public static String frequencyKey(String word) {
        int[] letterCounts = new int[26]; // one slot per letter: index 0 = 'a', index 25 = 'z'

        for (char ch : word.toLowerCase().toCharArray()) {
            letterCounts[ch - 'a']++; // subtract 'a' to convert char to 0-based index
        }

        // Serialise the array into a string using '#' as a delimiter.
        // Without a delimiter, counts like [12, 3] and [1, 23] would both become "123" — a collision!
        StringBuilder keyBuilder = new StringBuilder();
        for (int count : letterCounts) {
            keyBuilder.append(count).append('#');
        }
        return keyBuilder.toString();
    }

    public static void main(String[] args) {
        String[] testWords = {"listen", "silent", "enlist", "race", "care", "hello"};

        System.out.println("Word       | Sorted Key  | Frequency Key (truncated)");
        System.out.println("-----------|-------------|---------------------------");

        for (String word : testWords) {
            String sorted = sortedKey(word);
            String freq   = frequencyKey(word).substring(0, 20) + "..."; // trim for display
            System.out.printf("%-10s | %-11s | %s%n", word, sorted, freq);
        }
    }
}

import java.util.*;

public class GroupAnagrams {

    /**
     * Groups a list of words into sublists where every word in a sublist
     * is an anagram of the others.
     *
     * Approach: use a sorted-character string as a HashMap key.
     * Time:  O(n * k log k)  — n words, each sorted in O(k log k)
     * Space: O(n * k)        — storing all words in the map
     *
     * @param words the input array of lowercase strings
     * @return a list of groups, each group containing anagram siblings
     */
    public static List<List<String>> groupAnagrams(String[] words) {

        // Each unique sorted-key maps to a list of words that share it
        Map<String, List<String>> anagramBuckets = new HashMap<>();

        for (String word : words) {
            // Step 1: compute the canonical key for this word
            String canonicalKey = buildSortedKey(word);

            // Step 2: if no bucket exists for this key yet, create one on the fly
            // getOrDefault avoids a manual null-check — clean and readable
            anagramBuckets
                .computeIfAbsent(canonicalKey, k -> new ArrayList<>())
                .add(word);
        }

        // Return all bucket values as a list of lists
        return new ArrayList<>(anagramBuckets.values());
    }

    /** Sorts the characters of a word to produce a stable canonical key. */
    private static String buildSortedKey(String word) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }

    // ---------------------------------------------------------------
    // Bonus: O(n*k) frequency-array version — better for long strings
    // ---------------------------------------------------------------
    public static List<List<String>> groupAnagramsFast(String[] words) {
        Map<String, List<String>> anagramBuckets = new HashMap<>();

        for (String word : words) {
            String canonicalKey = buildFrequencyKey(word);
            anagramBuckets
                .computeIfAbsent(canonicalKey, k -> new ArrayList<>())
                .add(word);
        }

        return new ArrayList<>(anagramBuckets.values());
    }

    /** Produces a frequency-count key — O(k), no sorting needed. */
    private static String buildFrequencyKey(String word) {
        int[] charFrequencies = new int[26];

        for (char ch : word.toCharArray()) {
            charFrequencies[ch - 'a']++; // map 'a'->0, 'b'->1, ... 'z'->25
        }

        // Serialise with '#' delimiter to avoid count-boundary collisions
        StringBuilder key = new StringBuilder();
        for (int frequency : charFrequencies) {
            key.append(frequency).append('#');
        }
        return key.toString();
    }

    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};

        System.out.println("Input words: " + Arrays.toString(words));
        System.out.println();

        List<List<String>> groupedBySortedKey = groupAnagrams(words);
        System.out.println("Grouped (sorted-key approach):");
        for (List<String> group : groupedBySortedKey) {
            System.out.println("  " + group);
        }

        System.out.println();

        List<List<String>> groupedByFrequency = groupAnagramsFast(words);
        System.out.println("Grouped (frequency-key approach):");
        for (List<String> group : groupedByFrequency) {
            System.out.println("  " + group);
        }

        // Edge case: single word, no anagram siblings
        String[] singleWord = {"hello"};
        List<List<String>> singleResult = groupAnagrams(singleWord);
        System.out.println();
        System.out.println("Single word input: " + singleResult);

        // Edge case: all words are anagrams of each other
        String[] allAnagrams = {"abc", "bca", "cab", "bac"};
        List<List<String>> allSameGroup = groupAnagrams(allAnagrams);
        System.out.println("All anagrams input: " + allSameGroup);
    }
}

import java.util.*;

/**
 * Real-world example: detect which CSV file schemas are equivalent
 * (same columns, different order) using the anagram-grouping pattern.
 *
 * This is the same algorithm as group anagrams — just applied to
 * comma-separated column headers instead of single words.
 */
public class SchemaGrouper {

    /**
     * Groups file schemas that contain the same columns (regardless of order).
     * Each schema is a comma-separated string of column names.
     *
     * @param schemas array of schema strings, e.g. "name,age,city"
     * @return groups of schema strings that are column-equivalent
     */
    public static Map<String, List<String>> groupEquivalentSchemas(String[] schemas) {
        Map<String, List<String>> equivalenceGroups = new HashMap<>();

        for (String schema : schemas) {
            // Split on comma, sort the column names, rejoin — same idea as sorted char key
            String[] columns = schema.split(",");
            Arrays.sort(columns);                         // sort column names alphabetically
            String canonicalSchema = String.join(",", columns); // canonical fingerprint

            equivalenceGroups
                .computeIfAbsent(canonicalSchema, k -> new ArrayList<>())
                .add(schema);                             // bucket the original (unsorted) schema
        }

        return equivalenceGroups;
    }

    public static void main(String[] args) {
        // Simulating schemas arriving from different data sources
        String[] incomingSchemas = {
            "name,age,city",       // source A
            "age,city,name",       // source B — same columns, different order
            "city,name,age",       // source C — same again
            "id,email,phone",      // source D — different schema entirely
            "phone,id,email",      // source E — same as D, reordered
            "name,salary"          // source F — unique schema
        };

        Map<String, List<String>> groups = groupEquivalentSchemas(incomingSchemas);

        System.out.println("Equivalent schema groups:");
        System.out.println("=========================");

        int groupNumber = 1;
        for (Map.Entry<String, List<String>> entry : groups.entrySet()) {
            System.out.println("Group " + groupNumber + " (canonical: " + entry.getKey() + ")");
            for (String schema : entry.getValue()) {
                System.out.println("   -> " + schema);
            }
            groupNumber++;
        }
    }
}