[ADSx] - MostFrequentSubstring

import java.io.IOException;
import java.util.Scanner;

class MapEntry<K extends Comparable<K>, E> implements Comparable<K> {

    K key;
    E value;

    public MapEntry(K key, E val) {
        this.key = key;
        this.value = val;
    }

    public int compareTo(K that) {
        @SuppressWarnings("unchecked")
        MapEntry<K, E> other = (MapEntry<K, E>) that;
        return this.key.compareTo(other.key);
    }

    public String toString() {
        return "(" + key + "," + value + ")";
    }
}

class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

class CBHT<K extends Comparable<K>, E> {

    public SLLNode<MapEntry<K, E>>[] buckets;

    @SuppressWarnings("unchecked")
    public CBHT(int m) {
        buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % buckets.length;
    }

    public SLLNode<MapEntry<K, E>> search(K targetKey) {
        int b = hash(targetKey);
        for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
            if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
                return curr;
        }
        return null;
    }

    public E searchValue(K targetKey) {
        int b = hash(targetKey);
        for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
            if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
                return curr.element.value;
        }
        return null;
    }

    public void insert(K key, E val) {        // Insert the entry <key, val> into this CBHT.
        MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
        int b = hash(key);
        for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
            if (key.equals(((MapEntry<K, E>) curr.element).key)) {
                curr.element = newEntry;
                return;
            }
        }
        buckets[b] = new SLLNode<MapEntry<K, E>>(newEntry, buckets[b]);
    }

    public void delete(K key) {
        int b = hash(key);
        for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
            if (key.equals(((MapEntry<K, E>) curr.element).key)) {
                if (pred == null)
                    buckets[b] = curr.succ;
                else
                    pred.succ = curr.succ;
                return;
            }
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < buckets.length; i++) {
            sb.append(i).append(":");
            for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
                sb.append(curr.element.key).append(" -> ");
                sb.append(curr.element.value).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public static <K extends Comparable<K>, E extends Number> // E extends NUMBER
    String mostFrequentSubstring(SLLNode<MapEntry<K, E>>[] buckets) {
        String maxString = "";
        int maxFrequency = Integer.MIN_VALUE;
        for (int i = 0; i < buckets.length; i++) {
            for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
                E value = curr.element.value;
                String key = curr.element.key.toString();
                if (value.intValue() > maxFrequency) {
                    maxFrequency = value.intValue();
                    maxString = key;
                }
                // if it's smaller we don't care, because we're looking for MAX
                else if (value.intValue() == maxFrequency) {
                    // if equal frequency return the longest
                    if (key.length() > maxString.length()) {
                        maxFrequency = value.intValue();
                        maxString = key;
                    } else if (key.length() == maxString.length()) {
                        if (key.compareTo(maxString) < 0) { // same length but different letters
                            maxFrequency = value.intValue();
                            maxString = key; // get last longest string
                        }
                    }
                }
            }
        }
        return maxString;
    }

}

public class MostFrequentSubstring {
    public static void main(String[] args) throws IOException {
        CBHT<String, Integer> cbht = new CBHT<>(300);
        Scanner scanner = new Scanner(System.in);

        String word = scanner.nextLine().trim();

        for (int i = 0; i < word.length(); i++) {
            for (int j = i + 1; j <= word.length(); j++) {
                String subString = word.substring(i, j);
                Integer searched = cbht.searchValue(subString);
                if (searched == null) {
                    cbht.insert(subString, 1);
                } else {
                    cbht.insert(subString, searched + 1);
                }
            }
        }

        //System.out.println(cbht);

        System.out.println(CBHT.mostFrequentSubstring(cbht.buckets));

    }
}


/**
 * For a given string, find the most frequent substring. If two substrings have the same frequency, then print the longer one, and if they are the same, print the one higher lexicographically.
 * <p>
 * Example: For the string "abc" substrings are "a", "b", "c", "ab", "bc", "abc". All have the same frequency, but "abc" is the longest.
 * <p>
 * Name of the class (Java): mostFrequentSubstring.
 */