package com.helloworld;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Main {
    private static final Map<String, String> REPLACEMENTS = new HashMap<String, String>() {
        private static final long serialVersionUID = 1L;

        {
            put("ABW", " Aruba ");
            put("AFG", " Afghanistan ");
            put("AGO", " Angola ");
            put("AIA", " Anguilla ");
            put("ALA", " Åland Islands ");
            put("ALB", " Albania ");
            put("AND", " Andorra ");
            put("ARE", " United Arab Emirates ");
            put("ARG", " Argentina ");
            put("ARM", " Armenia ");
            put("ASM", " American Samoa ");
            put("ATA", " Antarctica ");
            put("ATF", " French Southern Territories ");
            put("ATG", " Antigua and Barbuda ");
            put("AUS", " Australia ");
            put("AUT", " Austria ");
            put("AZE", " Azerbaijan ");
            put("BDI", " Burundi ");
            put("BEL", " Belgium ");
            put("BEN", " Benin ");
            put("BES", " Bonaire, Sint Eustatius and Saba ");
            put("BFA", " Burkina Faso ");
            put("BGD", " Bangladesh ");
            put("BGR", " Bulgaria ");
            put("BHR", " Bahrain ");
            put("BHS", " Bahamas ");
            put("BIH", " Bosnia and Herzegovina ");
            put("BLM", " Saint Barthélemy ");
            put("BLR", " Belarus ");
            put("BLZ", " Belize ");
            put("BMU", " Bermuda ");
            put("BOL", " Plurinational State of Bolivia, ");
            put("BRA", " Brazil ");
            put("BRB", " Barbados ");
            put("BRN", " Brunei Darussalam ");
            put("BTN", " Bhutan ");
            put("BVT", " Bouvet Island ");
            put("BWA", " Botswana ");
            put("CAF", " Central African Republic ");
            put("CAN", " Canada ");
            put("CCK", " Cocos (Keeling) Islands ");
            put("CHE", " Switzerland ");
            put("CHL", " Chile ");
            put("CHN", " China ");
            put("CIV", " Côte d'Ivoire ");
            put("CMR", " Cameroon ");
            put("COD", "  the Democratic Republic of the Congo ");
            put("COG", " Congo ");
            put("COK", " Cook Islands ");
            put("COL", " Colombia ");
            put("COM", " Comoros ");
            put("CPV", " Cabo Verde ");
            put("CRI", " Costa Rica ");
            put("CUB", " Cuba ");
            put("CUW", " Curaçao ");
            put("CXR", " Christmas Island ");
            put("CYM", " Cayman Islands ");
            put("CYP", " Cyprus ");
            put("CZE", " Czechia ");
            put("DEU", " Germany ");
            put("DJI", " Djibouti ");
            put("DMA", " Dominica ");
            put("DNK", " Denmark ");
            put("DOM", " Dominican Republic ");
            put("DZA", " Algeria ");
            put("ECU", " Ecuador ");
            put("EGY", " Egypt ");
            put("ERI", " Eritrea ");
            put("ESH", " Western Sahara ");
            put("ESP", " Spain ");
            put("EST", " Estonia ");
            put("ETH", " Ethiopia ");
            put("FIN", " Finland ");
            put("FJI", " Fiji ");
            put("FLK", " Falkland Islands (Malvinas) ");
            put("FRA", " France ");
            put("FRO", " Faroe Islands ");
            put("FSM", " Federated States of Micronesia, ");
            put("GAB", " Gabon ");
            put("GBR", " United Kingdom ");
            put("GEO", " Georgia ");
            put("GGY", " Guernsey ");
            put("GHA", " Ghana ");
            put("GIB", " Gibraltar ");
            put("GIN", " Guinea ");
            put("GLP", " Guadeloupe ");
            put("GMB", " Gambia ");
            put("GNB", " Guinea-Bissau ");
            put("GNQ", " Equatorial Guinea ");
            put("GRC", " Greece ");
            put("GRD", " Grenada ");
            put("GRL", " Greenland ");
            put("GTM", " Guatemala ");
            put("GUF", " French Guiana ");
            put("GUM", " Guam ");
            put("GUY", " Guyana ");
            put("HKG", " Hong Kong ");
            put("HMD", " Heard Island and McDonald Islands ");
            put("HND", " Honduras ");
            put("HRV", " Croatia ");
            put("HTI", " Haiti ");
            put("HUN", " Hungary ");
            put("IDN", " Indonesia ");
            put("IMN", " Isle of Man ");
            put("IND", " India ");
            put("IOT", " British Indian Ocean Territory ");
            put("IRL", " Ireland ");
            put("IRN", " Islamic Republic of Iran, ");
            put("IRQ", " Iraq ");
            put("ISL", " Iceland ");
            put("ISR", " Israel ");
            put("ITA", " Italy ");
            put("JAM", " Jamaica ");
            put("JEY", " Jersey ");
            put("JOR", " Jordan ");
            put("JPN", " Japan ");
            put("KAZ", " Kazakhstan ");
            put("KEN", " Kenya ");
            put("KGZ", " Kyrgyzstan ");
            put("KHM", " Cambodia ");
            put("KIR", " Kiribati ");
            put("KNA", " Saint Kitts and Nevis ");
            put("KOR", " Republic of Korea, ");
            put("KWT", " Kuwait ");
            put("LAO", " People's Democratic Republic Lao ");
            put("LBN", " Lebanon ");
            put("LBR", " Liberia ");
            put("LBY", " Libya ");
            put("LCA", " Saint Lucia ");
            put("LIE", " Liechtenstein ");
            put("LKA", " Sri Lanka ");
            put("LSO", " Lesotho ");
            put("LTU", " Lithuania ");
            put("LUX", " Luxembourg ");
            put("LVA", " Latvia ");
            put("MAC", " Macao ");
            put("MAF", " Saint Martin (French part) ");
            put("MAR", " Morocco ");
            put("MCO", " Monaco ");
            put("MDA", " Moldova, Republic of ");
            put("MDG", " Madagascar ");
            put("MDV", " Maldives ");
            put("MEX", " Mexico ");
            put("MHL", " Marshall Islands ");
            put("MKD", " the former Yugoslav Republic of Macedonia, ");
            put("MLI", " Mali ");
            put("MLT", " Malta ");
            put("MMR", " Myanmar ");
            put("MNE", " Montenegro ");
            put("MNG", " Mongolia ");
            put("MNP", " Northern Mariana Islands ");
            put("MOZ", " Mozambique ");
            put("MRT", " Mauritania ");
            put("MSR", " Montserrat ");
            put("MTQ", " Martinique ");
            put("MUS", " Mauritius ");
            put("MWI", " Malawi ");
            put("MYS", " Malaysia ");
            put("MYT", " Mayotte ");
            put("NAM", " Namibia ");
            put("NCL", " New Caledonia ");
            put("NER", " Niger ");
            put("NFK", " Norfolk Island ");
            put("NGA", " Nigeria ");
            put("NIC", " Nicaragua ");
            put("NIU", " Niue ");
            put("NLD", " Netherlands ");
            put("NOR", " Norway ");
            put("NPL", " Nepal ");
            put("NRU", " Nauru ");
            put("NZL", " New Zealand ");
            put("OMN", " Oman ");
            put("PAK", " Pakistan ");
            put("PAN", " Panama ");
            put("PCN", " Pitcairn ");
            put("PER", " Peru ");
            put("PHL", " Philippines ");
            put("PLW", " Palau ");
            put("PNG", " Papua New Guinea ");
            put("POL", " Poland ");
            put("PRI", " Puerto Rico ");
            put("PRK", " Democratic People's Republic of Korea, ");
            put("PRT", " Portugal ");
            put("PRY", " Paraguay ");
            put("PSE", " State of Palestine, ");
            put("PYF", " French Polynesia ");
            put("QAT", " Qatar ");
            put("REU", " Réunion ");
            put("ROU", " Romania ");
            put("RUS", " Russian Federation ");
            put("RWA", " Rwanda ");
            put("SAU", " Saudi Arabia ");
            put("SDN", " Sudan ");
            put("SEN", " Senegal ");
            put("SGP", " Singapore ");
            put("SGS", " South Georgia and the South Sandwich Islands ");
            put("SHN", " Saint Helena, Ascension and Tristan da Cunha ");
            put("SJM", " Svalbard and Jan Mayen ");
            put("SLB", " Solomon Islands ");
            put("SLE", " Sierra Leone ");
            put("SLV", " El Salvador ");
            put("SMR", " San Marino ");
            put("SOM", " Somalia ");
            put("SPM", " Saint Pierre and Miquelon ");
            put("SRB", " Serbia ");
            put("SSD", " South Sudan ");
            put("STP", " Sao Tome and Principe ");
            put("SUR", " Suriname ");
            put("SVK", " Slovakia ");
            put("SVN", " Slovenia ");
            put("SWE", " Sweden ");
            put("SWZ", " Swaziland ");
            put("SXM", " Sint Maarten (Dutch part) ");
            put("SYC", " Seychelles ");
            put("SYR", " Syrian Arab Republic ");
            put("TCA", " Turks and Caicos Islands ");
            put("TCD", " Chad ");
            put("TGO", " Togo ");
            put("THA", " Thailand ");
            put("TJK", " Tajikistan ");
            put("TKL", " Tokelau ");
            put("TKM", " Turkmenistan ");
            put("TLS", " Timor-Leste ");
            put("TON", " Tonga ");
            put("TTO", " Trinidad and Tobago ");
            put("TUN", " Tunisia ");
            put("TUR", " Turkey ");
            put("TUV", " Tuvalu ");
            put("TWN", " Taiwan Province of China ");
            put("TZA", " United Republic of Tanzania, ");
            put("UGA", " Uganda ");
            put("UKR", " Ukraine ");
            put("UMI", " United States Minor Outlying Islands ");
            put("URY", " Uruguay ");
            put("USA", " United States of America ");
            put("UZB", " Uzbekistan ");
            put("VAT", " Holy See ");
            put("VCT", " Saint Vincent and the Grenadines ");
            put("VEN", " Bolivarian Republic of Venezuela, ");
            put("VGB", " British Virgin Islands, ");
            put("VIR", " U.S. Virgin Islands, ");
            put("VNM", " Viet Nam ");
            put("VUT", " Vanuatu ");
            put("WLF", " Wallis and Futuna ");
            put("WSM", " Samoa ");
            put("YEM", " Yemen ");
            put("ZAF", " South Africa ");
            put("ZMB", " Zambia ");
            put("ZWE", " Zimbabwe ");
        }
    };

    class ReplacementInfo {
        private int startIndex;
        private int endIndex;
        private String replacement;

        public ReplacementInfo(int startIndex, int endIndex, String replacement) {
            super();
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.replacement = replacement;
        }

        public int getStartIndex() {
            return startIndex;
        }

        public void setStartIndex(int startIndex) {
            this.startIndex = startIndex;
        }

        public int getEndIndex() {
            return endIndex;
        }

        public void setEndIndex(int endIndex) {
            this.endIndex = endIndex;
        }

        public String getReplacement() {
            return replacement;
        }

        public void setReplacement(String replacement) {
            this.replacement = replacement;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getOuterType().hashCode();
            result = prime * result + endIndex;
            result = prime * result + ((replacement == null) ? 0 : replacement.hashCode());
            result = prime * result + startIndex;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            ReplacementInfo other = (ReplacementInfo) obj;
            if (!getOuterType().equals(other.getOuterType()))
                return false;
            if (endIndex != other.endIndex)
                return false;
            if (replacement == null) {
                if (other.replacement != null)
                    return false;
            } else if (!replacement.equals(other.replacement))
                return false;
            if (startIndex != other.startIndex)
                return false;
            return true;
        }

        private Main getOuterType() {
            return Main.this;
        }

        @Override
        public String toString() {
            return "ReplacementInfo [startIndex=" + startIndex + ", endIndex=" + endIndex + ", replacement="
                    + replacement + "]";
        }

    }

    public String replace(String str, Map<String, String> replacementMap) {
        List<ReplacementInfo> replacementInfo = new LinkedList<>();

        for (Entry<String, String> entry : replacementMap.entrySet()) {
            int idx = -1;
            do {
                idx = str.indexOf(entry.getKey(), idx + 1);
                if (idx != -1) {
                    replacementInfo.add(new ReplacementInfo(idx, idx + entry.getKey().length(), entry.getValue()));
                }
            } while (idx != -1);
        }

        if (replacementInfo.isEmpty()) {
            return str;
        }

        Collections.sort(replacementInfo, new Comparator<ReplacementInfo>() {
            @Override
            public int compare(ReplacementInfo o1, ReplacementInfo o2) {
                return o1.startIndex - o2.startIndex;
            }
        });

        int deltaGrowth = replacementInfo.stream()
                .mapToInt(ri -> ri.getReplacement().length() - (ri.getEndIndex() - ri.getStartIndex())).sum();

        StringBuffer strBuffer = new StringBuffer(str.length() + deltaGrowth);
        ReplacementInfo prev = null;
        for (ReplacementInfo cur : replacementInfo) {
            if (prev == null) {
                if (cur.getStartIndex() > 0) {
                    strBuffer.append(str.substring(0, cur.getStartIndex()));
                }
            } else if (prev.getEndIndex() < cur.getStartIndex()) {
                strBuffer.append(str.substring(prev.getEndIndex(), cur.getStartIndex()));
            }

            strBuffer.append(cur.replacement);

            prev = cur;
        }
        if (prev.getEndIndex() < str.length()) {
            strBuffer.append(str.substring(prev.getEndIndex(), str.length()));
        }

        return strBuffer.toString();
    }

    public void handleMain(String args[]) {
        String s = "Test CHN another BEL test";
        System.out.println(s);
        System.out.println(replace(s, REPLACEMENTS));
    }

    public static void main(String args[]) {
        new Main().handleMain(args);
    }
}