n と k が大きすぎないため、これがメモリに収まると仮定します。
最初の文字が削除されたセット、2 番目の文字が削除されたセット、3 番目の文字が削除されたセットなどを用意します。技術的には、これは文字列からカウントへのマップである必要があります。
リストを実行し、現在の要素を各マップに追加するだけです (明らかに該当する文字を最初に削除します) (既に存在する場合は、count を totalPairs に追加し、1 ずつ増やします)。
次に、totalPairs が目的の値です。
編集：
複雑：
これはする必要がありますO(n.k.logn)。
HashMap理論的な複雑さのために、ソートされたマップの代わりに、ハッシュを使用するマップ (Java など) を使用できますO(nk)(ただし、一般に、ハッシュ マップはソートされたツリーベースのマップよりも遅いことがわかっています)。
改善：
これに対する小さな変更は、最初の 2 文字を削除して 2 つのマップにすることです。1 つは最初の文字を削除し、もう 1 つは 2 番目の文字を削除し、3 番目と 4 番目の文字も同様にします。
次に、これらを 4 文字を削除してマップに配置し、それらを 8 文字を削除してマップに配置し、最大で半分の文字を削除します。
これの複雑さは次のとおりです。
最大 k 個の要素を含む 2 つの並べ替えられたセットに 2 つのルックアップを行います (各半分について)。
これらのそれぞれについて、(四半期ごとに) 2 つのソートされたセットへの 2 つのルックアップを再度実行します。
したがって、ルックアップの数は 2 + 4 + 8 + ... + k/2 + k であり、これはO(k).
ここで間違っているかもしれませんが、最悪の場合、特定のマップの要素数は ですn。しかし、これにより、他のすべてのマップは 1 つの要素しか持たO(logn)なくnなりn.kます。
だから私はそれだと思いますO(n.(logn + k))。
.
編集2：
私のマップの例（改善なし）：
(x-1)xはにマップすることを意味します1。
あるとしましょうabcd, abdd, adcb, adcd, aecd。
最初のマップは(bcd-1), (bdd-1), (dcb-1), (dcd-1), (ecd-1).
2 番目のマップは次のようになります(acd-3), (add-1), (acb-1)(4 番目と 5 番目の値は既に存在するため、インクリメントします)。
3 番目のマップ : (abd-2), (adb-1), (add-1), (aed-1)(2 番目は既に存在します)。
4 番目のマップ : (abc-1), (abd-1), (adc-2), (aec-1)(4 番目は既に存在します)。
totalPairs = 0
2 番目のマップには - acd、4 番目には 1 を追加し、5 番目には 2 を追加します。
totalPairs = 3
3 番目のマップについては - abd、2 番目については 1 を追加します。
totalPairs = 4
4 番目のマップについては - adc、4 番目については 1 を追加します。
totalPairs = 5.
改善されたマップの部分的な例:
上記と同じ入力。
最初の 2 文字のマップが削除され、1 番目と 2 番目の文字のマップが削除されました:
(cd-{ {(bcd-1)}, {(acd-1)} }),
(dd-{ {(bdd-1)}, {(add-1)} }),
(cb-{ {(dcb-1)}, {(acb-1)} }),
(cd-{ {(dcd-1)}, {(acd-1)} }),
(cd-{ {(ecd-1)}, {(acd-1)} })
上記は、cd1 つの要素(bcd-1)を含むマップと を含むマップの 2 つのマップにマップされた要素で構成されるマップ(acd-1)です。
ただし、4 番目と 5 番目はcd既に存在するため、上記を生成するのではなく、次のようにそのマップに追加されます。
(cd-{ {(bcd-1, dcd-1, ecd-1)}, {(acd-3)} }),
(dd-{ {(bdd-1)}, {(add-1)} }),
(cb-{ {(dcb-1)}, {(acb-1)} })