Question

Create a Java program to find which word has the maximum occurrence and
replace that word by a special symbol, say *.

Answer 1

package com.company;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// A class to store a Trie node
class WordNode
{
    // `count` and `key` is only set for leaf nodes
    // `key` stores the string, and `count` stores its frequency so far
    String key;
    int count;

    // each node stores a map to its child nodes
    Map<Character, WordNode> character = null;

    // Constructor
    WordNode() {
        character = new HashMap<>();
    }
}

class Main
{
    // Iterative function to insert a string into a Trie
    public static void insert(WordNode head, String str)
    {
        // start from the root node
        WordNode current = head;

        for (char c: str.toCharArray())
        {
            // create a new node if the path doesn't exist
            current.character.putIfAbsent(c, new WordNode());

            // go to the next node
            current = current.character.get(c);
        }

        // store key and its count in leaf nodes
        current.key = str;
        current.count += 1;
    }

    // Function to perform preorder traversal on a Trie and
    // find a word with the maximum frequency
    public static int preorder(WordNode curr, int maximum_Count, StringBuilder key)
    {
        // return false if Trie is empty
        if (curr == null) {
            return maximum_Count;
        }

        for (var entry: curr.character.entrySet())
        {
            // leaf nodes have a non-zero count
            if (maximum_Count < entry.getValue().count)
            {
                key.replace(0, key.length(), entry.getValue().key);
                maximum_Count = entry.getValue().count;
            }

            // recur for current node's children
            maximum_Count = preorder(entry.getValue(), maximum_Count, key);
        }

        return maximum_Count;
    }

    public static void main(String[] args)
    {
        // given set of keys
        List<String> dict = Arrays.asList(
                "kelly", "programmer", "coding", "we", "pro", "pro", "code",
                "nyamai", "codec", "codecs", "kelly", "codex", "codify",
                "kelly", "codes", "code", "kelly", "pro", "codec",
                "codeveloper", "codrive", "codec", "tree", "kelly"
        );

        // Insert all keys into a Trie
        WordNode head = new WordNode();
        for (String word: dict) {
            insert(head, word);
        }

        int count = 0;
        StringBuilder key = new StringBuilder();

        // perform preorder traversal on a Trie and find the key
        // with maximum frequency
        count = preorder(head, count, key);

        System.out.println("Word : " + key);
        System.out.println("Count: " + count);
        //Now replace where there is the word with maximum count with *
    }
}