358.文字列kの距離を離して並べ替える



358 Rearrange String K Distance Apart

トピック:
空でない文字列strと整数kが与えられた場合、同じ文字が互いに少なくとも距離kになるように文字列を再配置します。

すべての入力文字列は小文字で示されます。文字列を並べ替えることができない場合は、空の文字列 ''を返します。



例1:
str = ''、k = 3

結果: 'abcabc'



同じ文字は、互いに少なくとも3の距離にあります。
例2:
str = 'aaabc'、k = 3

回答: ''

文字列を並べ替えることはできません。
例3:
str = 'aaadbbcc'、k = 2



回答:「abacabcd」

別の可能な答えは次のとおりです: 'abcabcda'

同じ文字は、互いに少なくとも2の距離にあります。

回答:

/ / First record the char in str and its occurrence in the number, there is count [], use valid [] to record the minimum position of this char. / / Each time the largest count value is selected, append to the new string public int selectedValue(int[] count, int[] valid, int i) { int select = Integer.MIN_VALUE int val = -1 for (int j = 0 j 0 && i >= valid[j] && count[j] > select) { select = count[j] val = j } } return val } public String rearrangeString(String str, int k) { int[] count = new int[26] int[] valid = new int[26] / / Write down the number of each occurrence of char for (char c : str.toCharArray()) { count[c - 'a']++ } StringBuilder sb = new StringBuilder() for (int i = 0 i