[HackerRank]愈大愈好(Bigger is Greater)

題目描述

給定一個文字W，請重新排列W的字母使得它構成另一個文字S，且這個文字S的字典排序必須在文字W之後。由於可能會有很多種答案，請找出並輸出字典排序在最前面的那個文字。

原題網址

輸入格式

輸入的第一行為一個整數T，代表測試資料的數量，範圍在1到10⁵之間(包含1和10⁵)，接下來的T行每行都是一個文字W，長度在1到100之間(包含1到100)，且只由小寫英文字母組成。

輸出格式

重組文字S，找出字典排序在文字W之後的文字S。這個文字S可能有好幾個，請輸出字典排序在最前面的那個。如果找不到任何的文字S，輸出「no answer」。

範例輸入

範例輸出

額外解釋

第一組測試資料的文字W為「ab」，重新排列後可以找到符合題目要求的「ba」。
第二組測試資料的文字W為「bb」，不管怎麼排列都是「bb」，所以無法重新排列找到符合題目要求的文字，輸出「no answer」。
第三組測試資料的文字W為「hefg」，重新排列後可以找到符合題目要求的「hegf」。
第四組測試資料的文字W為「dhck」，重新排列後可以找到符合題目要求的「dhkc」。
第五組測試資料的文字W為「dkhc」，重新排列後可以找到符合題目要求的「hcdk」。

解題概念

這題雖然可以把文字W的所有組合都先找出來後再使用辭典排序進行排序，找出我們要的文字S，但這樣效能太差了，必須要使用更有效的方式來進行。

為了要快速找到重新排列後辭典排序會比原本文字W還要後面的組合，我們可以先定位好要重新排列的字元範圍。

舉例來說，「hefg」由於「f」比「g」還排在更前面，所以若將「f」和「g」調換的話可以讓文字的辭典排序更為後面，因次我們也只需要從第三個字元「f」嘗試重新組合即可，因為只需要找到大於原本文字W辭典順序的最小文字(此時i=3)。由於第三個字元「f」的位置只能和最後一個字元調換，所以可以確定我們要的文字就是「hegf」。

再舉一個例子，「dkhc」由於「h」比「c」還排在更後面，僅調換「h」和「c」的話是不會找到符合題目要求的文字的，所以要再更往前看一點。由於「k」比「h」還排在更後面，調換「k」和「h」是沒用的，調換「k」和「c」也是沒用的(因為「h」比「k」還要更前面，「c」一定比「k」還要更前面，調換後無論是「dchk」或是「dckh」都不會比原本的「dkhc」還要來得後面)，所以要再更往前看一點。由於「d」比「k」還排在更前面，所以若將「d」和「k」或是「k」之後的字元調換的話，所形成的文字「有可能」會比原本的「dkhc」還要來得後面，並把此時的位置記錄下來，在這個位置之前的字元均不會變動了。為了要再更縮小範圍，把「有可能」化為「一定」，還需從最後一個字元「c」開始到剛才找到的字元「d」，依序尋找字元「d」和是否排在這些字元的前面。由於「d」比「c」還排在更後面，所以要再更往前看一點。由於「d」比「h」還排在更前面，代表把「d」和「h」交換後可以得到比原本「dkhc」還要來得後面的文字，也就是「hkdc」。然而重新排列後，還可以再找到比「hkdc」更前面，卻又比「dkhc」還要更後面的字元組合。由於我們知道原本「d」字元所在位置，也就是目前「h」字元的所在位置，這個位置之前的字元均不必變動，且同樣是這個位置之後的字元是呈現遞減的排序狀態，所以只要將之後的字元進行反轉，變成遞減的辭典排序即可得到題目要求的文字。至於要如何快速將其從遞增反轉成遞減，我們可以將這段範圍的字元視為一個陣列，以中央反射的方式去進行元素的交換，也就是原本第一個元素(最小值)會跟到最後一個元素(最大)交換，而第二個元素(第二小值)則會跟倒數第二個元素(第二大值)交換，依此類推。

若要判斷文字W有沒有解答，在一開始定位的時候，如果無法找到前面的字元比後面的字元之辭典排序還更後面的話，代表原本的文字W已經是辭典排序在最後面的組合了。因此直接輸出「no answer」即可。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {
        final Scanner sc = new Scanner(System.in);
        final StringBuilder sb = new StringBuilder();
        int testCase = Integer.parseInt(sc.nextLine());
        while (testCase-- > 0) {
            final char[] s = sc.nextLine().toCharArray();

            int i = s.length - 1;
            while (i > 0 && s[i - 1] >= s[i]) {
                --i;
            }
            if (i == 0) {
                sb.append("no answer\n");
                continue;
            }
            int j = s.length - 1;
            while (j > i && s[i - 1] >= s[j]) {
                --j;
            }
            swap(s, i - 1, j);
            int c = (s.length - i) / 2;
            for (int k = 1; k <= c; ++k) {
                swap(s, i++, s.length - k);
            }
            for (i = 0; i < s.length; ++i) {
                sb.append(s[i]);
            }
            sb.append("\n");
        }
        System.out.print(sb.toString());
    }

    private static void swap(final char[] s, final int a, final int b) {
        final char temp = s[a];
        s[a] = s[b];
        s[b] = temp;
    }
}