leetcode -文字を繰り返しない最長の部分文字列のための

問題定義ヘッドleetcode problem#3 .
与えられた文字列に対して、最も長い部分文字列の長さを見つける必要があります.理解のために以下のサンプル入力と出力をリストしました.

Max() = 0
Max(a) = 1
Max(aa) = 1
Max(ab) = 2
Max(abca) = 3
Max(abcdefghijk) = 11
Max(abccabcde) = 5
Max(abccabdefghabcababcab) = 8

私たちは実際の部分文字列自体を必要としないが、長さを強調します.では、実行に移りましょう.

ブルートフォース
ブルートフォースアプローチは、文字列内で開始と終了のインデックスを選択し、各文字を自分自身に対して比較し、最大長を追跡するグローバル変数を持つことです.この解は、開始端インデックスおよび比較文字を選ぶための3つのループを含む.この解決策を考えず、アルゴリズム的アプローチに移しましょう.

解決-スライディングウィンドウ
サブセット問題のために、取るための方法のうちの1つは、摺動ウィンドウである.「スライド」ウィンドウでループを要素のサブセットに制限します.特定のグローバルポインタを維持することによって、同じノードを複数回再訪するのを避けます.我々は、異なる方法で我々の問題状況を再構築することができます.

We need the length of the substring, in other words, difference between two indices

心の上で、我々は以下の方法で我々のウインドウをセットアップします.エンドインデックス(i)は(0,n−1)両方の範囲で線形的に増加する.最後に、最後の出現に基づいて開始インデックスを更新します.我々は長さだけを必要とするので、インデックス間の違いは、トリックを行います.
命令セット

要素が既に存在する場合、必要に応じて開始ポインタを移動する

開始インデックスと終了インデックスと最大長の長さを計算する

各要素については、最新のエンカウンターインデックス

私は以下の解決を落としました、そして、チュートリアルは続きます.このスニペットを実行してみてくださいonline here .

    fun lengthOfLongestSubstring(s: String): Int {
        // Sliding window start pointer
        var start = 0
        // Result
        var max = 0
        // Occurance map
        var occ = mutableMapOf<Char, Int>()

        for ((i, c) in s.withIndex()) {

            if (occ.containsKey(c)) {
                // Found a clash, move the start pointer 
                // next to the previous occurance if applicable
                val seekPoint = occ[c]!! + 1
                start = Math.max(seekPoint, start)
            }

            val length = i - start + 1
            max = Math.max(length, max)

            // Update the map with latest occurance
            // when clash happen next time, use this index
            occ[c] = i
        }
        return max
    }

ウォークスルー
反復に関してwalkthorughを持ちましょう.

Given abcamnijabxyzzz, max-substring is mnijabxyz

#
スタート
終わり
チャー
サブシーケンス
長さ
0
0
0
エー
エー
1
1
0
1
b
ab
2
2
0
2
c
ABC
3
3
1
3
エー*
BCA
3
4
1
4
エム
BCAM
4
5
1
5
n
BCAMN
5
6
1
6
私
bcamni
6
7
1
7
J
BcamNij
7
8
4
8
エー*
マニジャ
5
9
4
9
B *
マニジャブ
6
10
4
10
X
ムニジャブ
7
11
4
11
Y
ムナジャビ
8
12
4
12
Z
ムニジャビザズ
9
13
13
13
Z *
Z
1
14
14
14
Z *
Z
1
0 - 2 -各要素をスキャンし、ルックアップマップに追加されます.衝突がないので、start indexは変更されません.
3 -ルックアップから我々は知って来るa 0番目のインデックスに遭遇しました.それで、startは( 0 + 1 )に調整される
4 - 7 -衝突がない、スタートはまだ1です.7回目の反復では、見ることができますbcamnij は現在の部分文字列です.アイアイファーストa を除くa が存在します.
8 -ルックアップから、我々は見つかりましたa は3番目のインデックスで最後に遭遇しました.通知は[ A , 0 ]が3で最後の遭遇の間[ a , 3 ]に更新されました.これは、我々がルックアップで最初に遭遇したインデックスを保つならば、それが複製を含むので重要です.今、我々は(3 + 1)へのスタートを更新します.
9 - 9で、我々は見つかりましたb が存在する1 . しかし、我々は1(1 + 1)でスタートを更新しません.それで、我々は2010年にスタートを保ちます4 . 一意性を検証するにはmnijab は現在の部分文字列です.場合は、我々は我々のスタートを更新した2 私たちはcamnijab — ヒアツーa sのプレゼント.
10 - 12 -これらの繰り返しを通じて文字列を文字列で文字列に追加します.開始インデックスを4 .
- 13z が識別される.だからインデックスは以前の出会い+ 1に調整⇨ 12 + 1 .部分文字列は単一文字です.二番目z .
14 -反復13と同じ.
注意:ウィンドウの動きとは別に、ルックアップと最大の長さは、各ステップで更新されます.それがアルゴリズムに対する明白なステップであるので、私はチュートリアルでスキップしました.部分文字列を表に印刷しましたが、最終的な結果は必要ありません.
...
ルックアップマップとスライディングウィンドウを用いて,o(n)への時間複雑度を減らした.空間の複雑さはo ( m )です.ここでMはユニークな文字集合です.
...
👨‍💻 ハッピーコーディング👩‍💻