@@ -0,0 +1,1371 @@
+/*%0A** https://code.google.com/codejam/contest/dashboard?c=4304486%0A** level: Med%0A** N%5E2 solution. can be done in N? or NlogN using sort? Yea, Think so..%0A*/%0A%0Aimport java.util.*;%0Aimport java.lang.*;%0Aimport java.io.*;%0A%0A/*%0A * idea: lastword == one subseq(x) + mirror of remaining subseq(x)%0A */%0Apublic class LastWords %7B%0A%09%0A%09public static void main(String%5B%5D args) %7B%0A%09%09Scanner in = new Scanner(System.in);%0A%09%09int N = in.nextInt();%0A%09%09for (int i = 1; i %3C= N; ++i) %7B%0A%09%09%09System.out.println(%22Case #%22 + i + %22: %22 + new Task().input(in).getLastWord());%0A%09%09%7D%0A%09%09in.close();%0A%09%7D%0A%0A%09static class Task %7B%0A%09%09String x;%0A%0A%09%09Task input(Scanner in) %7B%0A%09%09%09this.x = in.next().trim();%0A%09%09%09return this;%0A%09%09%7D%0A%09%09%0A%09%09String getLastWord() %7B%0A%09%09%09TreeMap%3CInteger, Boolean%3E map = new TreeMap%3C%3E();%0A%09%09%09StringBuilder y = new StringBuilder();%0A%09%09%09int maxIndex = x.length() - 1;%0A%09%09%09char maxChar = '-';%0A%09%09%09while (maxIndex %3E= 0) %7B%0A%09%09%09%09int nextMaxIndex = this.getMaxIndexLeft(maxIndex);%0A%09%09%09%09maxChar = x.charAt(nextMaxIndex);%0A%09%09%09%09y.append(maxChar);%0A%09%09%09%09map.put(nextMaxIndex, true);%0A%09%09%09%09maxIndex = nextMaxIndex - 1;%0A%09%09%09%7D%0A%09%09%09for (int i = 0; i %3C x.length(); ++i) %7B%0A%09%09%09%09if (!map.containsKey(i)) %7B%0A%09%09%09%09%09y.append(x.charAt(i));%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%09return y.toString();%0A%09%09%7D%0A%09%09%0A%09%09int getMaxIndexLeft(int r) %7B%0A%09%09%09int maxIndex = r;%0A%09%09%09while (r-- %3E 0) %7B%0A%09%09%09%09if (x.charAt(r) %3E x.charAt(maxIndex))%0A%09%09%09%09%09maxIndex = r;%0A%09%09%09%7D%0A%09%09%09return maxIndex;%0A%09%09%7D%0A%09%7D%0A%7D

Last words problem A codejam16