fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         String s = sc.next();
  8.         int[] cnt = new int[26];
  9.         for (char c : s.toCharArray()) {
  10.             cnt[c - 'a']++;
  11.         }
  12.         int[] U = new int[26];
  13.         U[25] = cnt[25];
  14.         for (int i = 24; i >= 0; i--) {
  15.             U[i] = Math.min(cnt[i], U[i + 1]);
  16.         }
  17.         int[] need = new int[26];
  18.         for (int i = 0; i < 26; i++) {
  19.             need[i] = U[i];
  20.         }
  21.         int[] curCount = new int[26];
  22.         for (int i = 0; i < 26; i++) {
  23.             curCount[i] = cnt[i];
  24.         }
  25.         StringBuilder stack = new StringBuilder();
  26.         for (char c : s.toCharArray()) {
  27.             int idx = c - 'a';
  28.             curCount[idx]--;
  29.             if (need[idx] <= 0) {
  30.                 continue;
  31.             }
  32.             while (stack.length() > 0) {
  33.                 char topChar = stack.charAt(stack.length() - 1);
  34.                 int topIdx = topChar - 'a';
  35.                 if (topChar > c && curCount[topIdx] > need[topIdx]) {
  36.                     stack.deleteCharAt(stack.length() - 1);
  37.                     need[topIdx]++;
  38.                 } else {
  39.                     break;
  40.                 }
  41.             }
  42.             stack.append(c);
  43.             need[idx]--;
  44.         }
  45.         System.out.println(stack.toString());
  46.     }
  47. }
Success #stdin #stdout 0.11s 54600KB
comments (?)
stdin
copy 
4
xyxz
stdout
copy 
xyz
https://ideone.com/kvdYBl
language:
Java (HotSpot 12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!