主題
題目連結：
題目意譯：
你被給定一個二元字串 s 以及一正整數 k。
回傳 s 中最長子序列之長度，其滿足將其視為一個二進位數字後其值小於等於 k。
注：
子序列可以包含前導零。
空字串之數值視為等於 0。
一個子序列為一字串藉由刪除零個或多個另一字串中的字元並且使剩餘字元的相對順序保持不變而得到。
限制：
1 ≦ s.length ≦ 1000
s[i] is either '0' or '1'.
1 ≦ k ≦ 10 ^ 9
範例測資：
範例 1：
輸入： s = "1001010", k = 5
輸出： 5
解釋： s 中其滿足將其視為一個二進位數字後其值小於等於 5 的最長子序列為 "00010"，其值於十進位中為 2。
注意到 "00100" 以及 "00101" 也是可行的，其依序分別在十進位中的值為 4 和 5。
該子序列的長度為 5，因此回傳 5。
範例 2：
輸入： s = "00101001", k = 1
輸出： 6
解釋： "000001" 為 s 中最長子序列，其滿足將其視為一個二進位數字後其值小於等於 1，因為該數字在十進位中之值為 1。
該子序列的長度為 6，因此回傳 6。
解題思維：
想法其實很單純——首先，只要看到 0 就取。也就是說，存在一組最佳解是包含 s 中所有的 0。
證明如下：
首先，如果 s 中沒有半個 0 則直接視為「包含」全部的 0。
假設現在有一個最佳解不包含所有的 0，其內容為 B1 B2 …… Bx（解的長度為 x）。
現在把任意一個落掉的 0 加進來，並假設「插入」的位置為 p（當然，不能隨便把這個 0 塞到任意位置，要使整個字串為 s 的一個子序列才行）。因此現在的「解」（現在不一定 ≦ k 了）的長相為
B1 B2 …… Bp 0 Bp+1 Bp+2 …… Bx
可以看到這對 Bp+1 Bp+2 …… Bx 的部分沒有影響，但是對 B1 B2 …… Bp 會有整體數值的影響（因為新插入的 0 使得這個部分全部往左移了一個位元）。
而現在整個數字依舊 ≦ k 的話，則代表我們得到一個長度更長的解。而這違反了一開始的解為最佳解的定義，所以這件事情並不成立；因此現在這個數字必定 > k，而此時只要把最高位（即最靠左）的 1 去掉即可使整體之值變為 ≦ k 的狀態（這部分就交給讀者自行思考，這邊避免篇幅冗長而略過此敘述之說明）。
因此我們得到了一個長度不變、數值 ≦ k 且比原先多包含一個 0 的新的最佳解。重複執行以上步驟便可以把所有的 0 都包含進來。
那如果看到 1 呢？。而這點就很單純，這是基於上面直接取 0 的策略可以得到：
很明顯，全部都是 0 的子序列必定可行。
此時要把 1 包含進來的話且又要使總數值 ≦ k，則此時應盡量取靠最右側（也就是越晚出現）的 1 越好（因為這樣數值越小）。
當取到沒有 1 可以取，或是取了之後必定大於 k 時就停止。此時即可得到一組最佳解，其長度即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
