TIRA 1.5 esimerkki

import java.util.*;
/*
    Ratkaisun idea: lähdetään rakentamaan uutta merkkijonoa
    merkki kerrallaan. Seuraava huomio on oleellinen: jos jotain
    merkkiä on jäljellä 1 enemmän kuin kaikkia muita merkkejä
    yhteensä, niin joudumme lisäämään sen. Esimerkiksi tilanteessa
    jossa jäljellä olevat kirjaimemme olisivat c,c,c,a,b joudumme
    käyttämään merkit a ja b erottamaan merkkejä c toisistaan.
    Sijoittaisimme ne siis merkkijonoon seuraavasti: cacbc.

    Algoritmi toimii seuraavasti: pidetään aina muistissa edellisessä
    indeksissä olevaa kirjainta. Sen lisäksi tarkistamme aina
    onko jotain kirjainta jäljellä yksi kappale enemmän kuin muita
    kirjaimia yhteensä. Jos tällainen kirjain löytyy, sijoitamme sen
    rakennettavan merkkijonon perälle. Muutoin sijoitamme merkkijonoon
    pienimmän kirjaimen, jota on jäljellä ja joka ei esiinny edellsisessä
    indeksissä.
*/
public class Main {
    public static String jarjestaMerkit(String mjono) {
        int n=mjono.length();

        int[] merkkien_esiintyvyys=new int[256];

        for(int i=0; i<n; i++)
            merkkien_esiintyvyys[mjono.charAt(i)]++;

        StringBuilder vastaus=new StringBuilder();

        int jaljella=n;
        int kirjain_vasemmalla=-1;

        while(jaljella!=0){

            boolean pakko=false;

            for(int i='A'; i<='Z'; i++){
                if(merkkien_esiintyvyys[i]*2==jaljella+1){
                    merkkien_esiintyvyys[i]--;
                    pakko=true;
                    vastaus.append((char)(i));
                    jaljella--;
                    kirjain_vasemmalla=i;
                    break;
                }
            }

            if(pakko)
                continue;

            for(int i='A'; i<='Z'; i++){
                if(merkkien_esiintyvyys[i]!=0&&i!=kirjain_vasemmalla){
                    merkkien_esiintyvyys[i]--;
                    vastaus.append((char)(i));
                    jaljella--;
                    kirjain_vasemmalla=i;
                    break;
                }
            }
        }
        return vastaus.toString();
    }

    public static void main(String[] args) {
        System.out.println(jarjestaMerkit("BAAACCC"));
        System.out.println(jarjestaMerkit("CBAED"));
        System.out.println(jarjestaMerkit("AXAXA"));
        System.out.println(jarjestaMerkit("CBAXXXX"));
    }
}