View difference between Paste ID: utenZdXZ and jNDdytcD

 import java.util.*;
-/*
+
-    Ratkaisun idea: lähdetään rakentamaan uutta merkkijonoa
+
-    merkki kerrallaan. Seuraava huomio on oleellinen: jos jotain
+    public static int getDoublePosStart(StringBuilder sb, int start, int startlen) {
-    merkkiä on jäljellä 1 enemmän kuin kaikkia muita merkkejä
+        for (; start < startlen; ++start) {
-    yhteensä, niin joudumme lisäämään sen. Esimerkiksi tilanteessa
+            if (sb.charAt(start) == sb.charAt(start - 1)) {
-    jossa jäljellä olevat kirjaimemme olisivat c,c,c,a,b joudumme
+                return start;
-    käyttämään merkit a ja b erottamaan merkkejä c toisistaan.
+
-    Sijoittaisimme ne siis merkkijonoon seuraavasti: cacbc.
+
         return -1;
-    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
+    public static int getDoublePosEnd(StringBuilder sb, int limit) {
-    kirjaimia yhteensä. Jos tällainen kirjain löytyy, sijoitamme sen
+        // for (int i = sb.length() - 1; i > limit; --i) {
-    rakennettavan merkkijonon perälle. Muutoin sijoitamme merkkijonoon
+        int i = sb.length() - 1;
-    pienimmän kirjaimen, jota on jäljellä ja joka ei esiinny edellsisessä
+        if (i > limit) {
-    indeksissä.
+            if (sb.charAt(i) == sb.charAt(i - 1)) {
-*/
+                return i;
             }
         }
-        int n=mjono.length();
+        return -1;
     }
-        int[] merkkien_esiintyvyys=new int[256];
+
     public static int getNonDoublePos(StringBuilder sb, char c, int oldpos) {
-        for(int i=0; i<n; i++)
+        for (int i = oldpos; i > 0; --i) {
-            merkkien_esiintyvyys[mjono.charAt(i)]++;
+            if (sb.charAt(i) != c && sb.charAt(i - 1) != c) {
                 return i;
-        StringBuilder vastaus=new StringBuilder();
+
         }
-        int jaljella=n;
+        return 0;
-        int kirjain_vasemmalla=-1;
+
 
-        while(jaljella!=0){
+    public static String xjarjestaMerkit(String mjono) {
         int amin = 255;
-            boolean pakko=false;
+        int amax = 0;
         int[] amounts = new int[256];
-            for(int i='A'; i<='Z'; i++){
+        for (int i = 0; i < mjono.length(); ++i) {
-                if(merkkien_esiintyvyys[i]*2==jaljella+1){
+            char c = mjono.charAt(i);
-                    merkkien_esiintyvyys[i]--;
+            ++amounts[c];
-                    pakko=true;
+            amin = Math.min(amin, c);
-                    vastaus.append((char)(i));
+            amax = Math.max(amax, c);
-                    jaljella--;
+
-                    kirjain_vasemmalla=i;
+
-                    break;
+        int[] firstcharloc = new int[256];
 
         boolean first = true;
         StringBuilder result = new StringBuilder();
-            if(pakko)
+        int lastpos = 1;
         for (char i = (char)amin; i <= amax; ++i) {
             if (amounts[i] <= 0) {
-            for(int i='A'; i<='Z'; i++){
+
-                if(merkkien_esiintyvyys[i]!=0&&i!=kirjain_vasemmalla){
+
-                    merkkien_esiintyvyys[i]--;
+
-                    vastaus.append((char)(i));
+            // optimizaion for first
-                    jaljella--;
+            if (first) {
-                    kirjain_vasemmalla=i;
+                for (int j = 0; j < amounts[i]; ++j) {
-                    break;
+                    result.append(i);
                 }
                 first = false;
                 continue;
-        return vastaus.toString();
+
 
             int startlen = result.length();
             for (int j = 0; j < amounts[i]; ++j) {
                 int samepos = getDoublePosStart(result, lastpos, startlen);
 
                 if (samepos >= 0) {
-        System.out.println(jarjestaMerkit("CBAXXXX"));
+                    result.insert(samepos, i);
                     lastpos = samepos + 1;
                     ++startlen;
                 } else {
                     firstcharloc[i]++;
                     result.append(i);
                     if (i == amax) {
                         int strend = result.length()-firstcharloc[i];
                         ++j;
                         for (; j < amounts[i]; ++j) {
                             int pos2 = getNonDoublePos(result, i, strend);
                             result.insert(pos2, i);
                             lastpos++;
                             strend = pos2;
                         }
                         break;
                     }
                 }
             }
         }
 
         char oldchar = result.charAt(result.length() - 1);
         int oldpos = result.length() - firstcharloc[oldchar];
         while (true) {
             int pos = getDoublePosEnd(result, lastpos);
             if (pos < 0) {
                 break;
             } else {
                 char c = result.charAt(pos);
                 if (c != oldchar) {
                     oldpos = result.length() - firstcharloc[c];
                 }
                 int pos2 = getNonDoublePos(result, c, oldpos);
                 result.deleteCharAt(pos);
                 result.insert(pos2, c);
                 lastpos++;
             }
         }
         return result.toString();
     }
 
 
 
     static int amin = 255;
     static int amax = 0;
     static int total = 0;
     static int[] amounts = new int[256];
 
     public static char getNextChar(char lastChar)
     {
         char next = 255;
         for (char i = (char)amin; i <= amax && total > 0; ++i) {
             if (amounts[i] <= 0) {
                 continue;
             }
             if (i == lastChar) {
                 continue;
             }
             if (amounts[i] > total/2) {
                 next = i;
                 break;
             }
             next = (char)Math.min(next, i);
         }
         --amounts[next];
         --total;
         return next;
     }
 
     public static String jarjestaMerkit(String mjono) {
         for (int i = 0; i < mjono.length(); ++i) {
             char c = mjono.charAt(i);
             ++amounts[c];
             ++total;
             amin = Math.min(amin, c);
             amax = Math.max(amax, c);
         }
 
         StringBuilder sb = new StringBuilder();
         char c = 0;
         while (total > 0)
         {
             c = getNextChar(c);
             sb.append(c);
         }
 
         return sb.toString();
     }
 
     public static void main(String[] args) {
         if (true) {
             suuri3();
             return;
         }
         System.out.println(jarjestaMerkit("AAABBB"));
         System.out.println(jarjestaMerkit("AAABBBCCCCCCCDDDDD"));
         System.out.println(jarjestaMerkit("BAAACCC"));
         System.out.println(jarjestaMerkit("CBAED"));
         System.out.println(jarjestaMerkit("AXAXA"));
     }
 
     public static void suuriTesti(String alku, String loppu) {
         String uusi = jarjestaMerkit(alku);
         System.out.println(uusi.equals(loppu));
         System.out.println(uusi);
         System.out.println(loppu);
         System.out.println(uusi.length());
         System.out.println(uusi.substring(uusi.length() - 200));
     }
 
     public static void suuri3() {
         int n = 99999;
         char[] t = new char[n];
         char[] u = new char[n];
         for (int i = 0; i < n; i++) {
             if (i % 2 == 0) {
                 t[i] = 'X';
             } else if (i < n / 2) {
                 t[i] = 'A';
             } else {
                 t[i] = 'B';
             }
             u[i] = t[i];
         }
         Arrays.sort(u);
         suuriTesti(new String(u), new String(t));
     }
 }