繰り返し文字から隣接する等しい文字がない可能なすべての文字列を返します。文字列

Question

一部の文字が連続して繰り返される英数字の文字列を指定すると、繰り返しのない文字を散らばらなければなりません。

input: aaaabbbcdd11 
Output: abababacd1d1 or any other valid combination. 

このような組み合わせがない場合、出力はありません。

この質問はインタビューで私に聞かれました。私はまだこのアルゴリズムを解決することができません。これが正しい質問であるかどうかわからない。私はこれを解決するために使用できる適切なアルゴリズム/データ構造を知るのが非常に面倒です。

ハッシュ（マップ）を作成して、すべての文字の数を維持できるようにしようとしました。

str = "aaaabbbcdd11" 
hashChrs = {} 
for item in list(str): 
    if item in hashChrs: 
     hashChrs[item] = hashChrs[item] + 1 
    else: 
     hashChrs[item] = 1 
print hashChrs 

{ ''：4 '1'：2 'C'：1、 'B'：3、 'D'：2}

最高周波数文字カウントであろう合計文字の半分以上が出力されません。

は今、私はマップ

Answer 1

天井回（文字列/ 2の長さ）よりも多く発生してもキャラクタが存在しない場合にのみ散乱させることができるを使用して、すべての所望の出力を印刷することはできませんよ。キャラクターがそれ以上に発生した場合、そのキャラクターを散らすことが不可能になる理由は分かりますか？ （以下の回答）

「abababa」は、文字「a」のインスタンスの最大数を交互に指定することで得られます"それは7文字、4に収まることができます。この数値は、式の上限（文字列の長さ/ 2）を使用して計算できます。

次のように今、アルゴリズムは次のとおりです。その後、逆rail fence cipher with 2 railsを使用し、彼らは文字列で表示されますどのくらいの頻度で文字を並べ替える（いわゆる「abcdabcabaは」「aaaabbbccd」になります）。つまり、ソートされた文字列を半分に分割します（長さが揃っている場合は半分に分割し、そうでない場合は前半に1文字以上の文字を分割します）。最後に文字列を作成し、最初の文字列から始まる各文字列の文字。したがって、 "aaaabbbccd"は "ababacacbd"になります。これがうまくいくことを証明するためにあなたに残しておきます。

これを行うには、逆のレールフェンスの下でさまざまなサイズの文字のブロックが発生する可能性があります。