ReplaceMap.java

import java.util.*;

public class ReplaceMap {
    private static Map<String, String> replacements;

    static {
        replacements = new HashMap<String, String>();
        replacements.put("ab", "Apple");
        replacements.put("bac", "Banana");
        replacements.put("cdea", "Cantalope");
        replacements.put("dabcd", "Date");
    }

    public ReplaceMap() {
        String phrase = "ab bac cdea dabcd ab bac cdea dabcd";

        System.out.println(replace(phrase, replacements));
    }

    public static List<String> asSortedList(Collection<String> c) {
        List<String> list = new ArrayList<String>(c);
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                if (a.length() < b.length()) {
                    return 1;
                } else if (a.length() > b.length()) {
                    return -1;
                } else {
                    return a.compareTo(b);
                }
            }
        });

        return list;
    }

    public static String replace(String it, Map<String, String> map) {
        StringBuilder sb = new StringBuilder();
        List<String> sortedKeys = asSortedList(map.keySet());
        System.out.printf("KEYS SORTED: %s\n", sortedKeys);
next:   while (it.length() > 0) {
            for (String k : sortedKeys) {
                if (it.startsWith(k)) {
                    // We have a match!
                    sb.append(map.get(k));
                    it = it.substring(k.length(), it.length());
                    continue next;
                }
            }
            // no match, advance one character
            sb.append(it.charAt(0));
            it = it.substring(1, it.length());
        }

        return sb.toString();
    }

    public static void main (String[] args) throws java.lang.Exception {
        new ReplaceMap();
    }
}