链接

给一个全是小写字母的字符串str，删除多余字符，使得每种字符只保留一个，并且让最终结果字符串字典序最小。

import java.util.Scanner;

public class Main {

    private static String solve(char[] str) {
        if (str == null || str.length == 0) {
            return "";
        }

        int[] hash = new int[256];
        int n = str.length;
        for (int i = 0; i < n; ++i) {
            hash[str[i] - 'a']++;
        }
        int l = 0, r = 0;
        StringBuilder ret = new StringBuilder();

        while (r < n) {
            /**
             * 已删除或未包含所有字符
             */
            if (hash[str[r] - 'a'] == -1 || --hash[str[r] - 'a'] != 0) {
                r++;
            } else {

                /**
                 * 窗口内最小字符
                 */
                int minIndex = l;
                for (int i = l; i <= r; ++i) {
                    if (str[i] < str[minIndex]) {
                        minIndex = i;
                    }
                }

                ret.append(str[minIndex]);

                /**
                 * 还原
                 */
                for (int i = minIndex + 1; i <= r; ++i) {
                    if (hash[str[i] - 'a'] != -1) {
                        hash[str[i] - 'a']++;
                    }
                }

                l = minIndex + 1;
                r = minIndex + 1;
            }
        }

        return ret.toString();
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.next();
            System.out.println(solve(s.toCharArray()));
        }
    }
}