題目

對于一個連續正整數組成的序列，可以將其拼接成一個字符串，再將字符串里的部分字符打亂順序。如序列8 9 10 11 12,拼接成的字符串為89101112,打亂一部分字符后得到90811211,原來的正整數10就被拆成了0和1。

現給定一個按如上規則得到的打亂字符的字符串，請將其還原成連續正整數序列，并輸出序列中最小的數字。

輸入描述

輸入一行，為打亂字符的字符串和正整數序列的長度，兩者間用空格分隔，字符串長度不超過200,正整數不超過1000，保證輸入可以還原成唯一序列。

輸出描述

輸出一個數字，為序列中最小的數字。

用例

輸入	輸出
19801211 5	8

思考

給出了有序序列的長度，因此可從整數 1 開始選取連續的給定長度的數字序列和打亂序列進行匹配，如果是組成成分完全相同的序列就終止選取序列循環，返回枚舉序列的起點數字，即序列中最小數字。這個在循環中枚舉起點選取固定長度序列操作就是滑動窗口思想的應用，窗口的大小就是給定的序列長度。問題是怎么比較選取有序序列和打亂的目標序列？我開始想到的做法竟然是把序列拆分成單個數字字符數組再轉成單個數字組成的數組從小到大排序后再連接成字符串和同樣這樣處理的目標字符串進行比較，完全相同就找到目標序列。如[9, 10, 11]->[9,1,0,1,1]->[0,1,1,1,9]->"01119"。這樣反復拆分字符串又排序，做法肯定不好。實際上比較兩個字符串的成分是否相同應該統計組成它們的0-9數字頻率是否相同，如果相同則它們的有序序列一定相同。定義一個數組，索引 0~9 對應的值為索引表示的數字出現的頻率，預先計算目標字符串的頻率數組 matchFreqs，每次移動窗口左邊界時開始更新選取的數字序列頻率數組 freqs，并比較 matchFreqs 和 freqs 頻率是否完全匹配，匹配則找到結果，然后返回窗口左邊界值。

算法過程

1. 統計目標字符串數字頻率：用長度為 10 的數組記錄 0-9 各數字出現次數。
2. 確定起始數字范圍：最大起始值設為1000-n（受題目條件限制）。
3. 遍歷檢查可能起始值：對每個起始數i，生成i到i+n-1的數字串，統計頻率并與目標對比。
4. 輸出匹配結果：找到頻率完全一致的起始值i，輸出即為最小數字。

時間復雜度：O (m + k×n)，m 為字符串長度，k 為遍歷次數（最多 1000）。

參考代碼

function solution() {const arr = readline().split(' ');const n = parseInt(arr[1]);const matchStr = arr[0];const matchFreqs = Array(10).fill(0);for (let num of matchStr) {matchFreqs[Number(num)]++;}const check = function(i, j) {let s = '';for (let k = i; k < j; k++) {s += k;}s = s.toString();const freqs = Array(10).fill(0);for (let c of s) {freqs[Number(c)]++;}for (let i = 0; i <= 9; i++) {if (freqs[i] !== matchFreqs[i]) {return false;}}return true;};for (let i = 1; i <= 1000-n; i++) {let j = i + n;if (check(i, j)) {console.log(i);return;}}}const cases = [`19801211 5`,
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});