删除多余的字符得到字典序最小的字符串

本文主要是介绍删除多余的字符得到字典序最小的字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

给一个全是小写字母的字符串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()));
        }
    }
}

这篇关于删除多余的字符得到字典序最小的字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！