題目描述

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



原題網址

輸入格式

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

輸出格式

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

範例輸入

5
ab
bb
hefg
dhck
dkhc

範例輸出

ba
no answer
hegf
dhkc
hcdk

額外解釋

第一組測試資料的文字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;
    }
}