再帰を使用せずに文字列内の繰り返し文字を削除する

Question

文字列が与えられます。その文字列から重複する文字を削除する関数を開発します。文字列の長さは任意です。あなたのアルゴリズムは空間になければなりません。あなたが望むなら、文字サイズに依存しない一定の余分なスペースを使うことができます。あなたのアルゴリズムは複雑でO（n）でなければなりません。

私の考えは、0番目のインデックスが文字aに対応し、25番目のインデックスが文字zに対応し、すべての要素を0に初期化する26のサイズの整数配列を定義することでした。 したがって、そして、我々が手紙に出会ったとき、そして望むインデックスの値を増やすだろう。

文字列をもう一度移動し、目的のインデックスの値が1ならば、それ以外の場合は文字を出力します。

このように、時間の複雑さはO（n）であり、使用されるスペースは文字列の長さに関係なく一定です!!

誰かがより効率的なアイデアを考え出すことができれば、とても役に立ちます！

Answer 1

追加の配列の代わりにビットセットを使用して、見つかった文字を追跡することもできます。どの文字（a-z以上）が許可されているかに応じて、それに応じてビットセットのサイズを決めます。これは、整数配列よりも少ないスペースを必要とする。

Answer 2

解決策はO（n）時間の基準に確実に合致します。許可されたアルファベットが大きい場合（Unicodeの文字数が100万文字を超える場合）非常に大きな配列ではなく、プレーンなハッシュを使用できます。ここで（！最適化されていない）Rubyであなたのアルゴリズムは次のとおりです。

def undup(s) 
    seen = Hash.new(0) 
    s.each_char {|c| seen[c] += 1} 
    result = "" 
    s.each_char {|c| result << c if seen[c] == 1} 
    result 
end 

puts(undup "") 
puts(undup "abc") 
puts(undup "Olé") 
puts(undup "asdasjhdfasjhdfasbfdasdfaghsfdahgsdfahgsdfhgt") 

それは、文字列を2回通過を行い、ハッシュ・ルックアップが線形よりも小さいので、あなたは良いです。

Hashtable（配列のようなもの）はアルファベットの上に拘束されているため、定数でも大文字ではありますが、スペースを使用すると言うことができます。アルファベットのサイズが文字列のサイズよりも大きい場合でも、それは一定のスペースとしてカウントされます。

この問題には多くのバリエーションがあり、その多くは楽しいものです。真にそれを行うには、まずソートすることができます。これはO（n log n）を与える。マージソートには、マージ中にダンプを無視するバリエーションがあります。実際、この「外部ハッシュテーブルなし」の制限は、Algorithm: efficient way to remove duplicate integers from an array（インタビューのタグも付いています）に表示されます。

もう1つの一般的なインタビューの質問は、単純な文字列で始まり、大文字と小文字の区別がついています。今は100万文字の文字列です。ビッグデータの検討を開始すると、非常に興味深いものになります。

とにかく、あなたのアイデアはかなり良いです。一般的に次のように微調整することができます：辞書ではなく、集合を使用します。文字列を辿る。各文字について、それがセットに含まれていない場合は、それを追加します。そうであれば、を削除してください。セットは、スペースを取らず、カウンタを必要とせず、アルファベットが小さく、このアルゴリズムが2回のパスを必要としない場合、ビットセットとして実装できます。

Python実装：P任意のプログラミング言語の制約：http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/