重複のない最長部分文字列
ウィンドウ内で最後に出現した位置を追跡します
「重複のない最長部分文字列」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
典型的なウィンドウ問題
同じ文字を含まない最長の部分文字列を求めます。これはほぼすべてのオンラインジャッジで登場する、スライディングウィンドウの代表的な問題です。🔤
全探索の罠
すべての部分文字列について重複を確認すると、計算量はおよそO(n^2)以上になります。長い文字列では遅すぎるため、より賢い走査が必要です。
重複しない文字のウィンドウ
常に異なる文字だけを含むウィンドウを保ちます。右側から拡張し、重複が現れたら、それがなくなるまで左側から縮小します。
最後に現れた位置を記憶する
各文字の最後のインデックスを辞書に保存します。これにより、走査中にその文字が最後に現れた位置を即座に確認できます。
last = {}
left = 0
best = 0各文字を走査する
right を使って文字列をループし、各ステップでインデックスと文字の両方を読み取ります。これによってウィンドウを 1 位置ずつ前に進めます。
for right, ch in enumerate(s):左ポインターをジャンプさせる
その文字が現在のウィンドウの内側で見つかっていた場合は、left をその文字の最後の位置の直後まで移動します。これにより、重複を 1 回の移動で取り除けます。
if ch in last and last[ch] >= left:
left = last[ch] + 1更新して長さを測る
この文字の新しい位置を記録すると、left から right までのウィンドウには重複がなくなります。その長さは right - left + 1 です。
last[ch] = right
best = max(best, right - left + 1)条件チェックが重要な理由
last[ch] >= left のチェックは不可欠です。これがないと、ウィンドウの外側にある古い位置によって left が誤って後ろへ戻されてしまいます。
時間も空間も線形
各文字は 1 回だけ訪れ、left は前方にしか進まないため、走査は O(n) です。辞書は異なる文字の個数分の領域を使います。
考慮すべき端のケース
空の文字列の答えは 0 で、同じ文字が 1 文字だけ繰り返される文字列の答えは 1 です。提出前に両方を確認して、見落としによる WA を避けてください。
再利用できるパターン
最後に見つかった位置のマップと、ジャンプする left ポインターの組み合わせは、異なる要素の個数に関する多くの問題に応用できます。たとえば、重複を 1 回まで許すウィンドウなどです。
確認
最長の重複しない部分文字列を探しながら、各文字の最後のインデックスを追跡します。
まとめ
重複しない文字のウィンドウをスライドさせ、各文字の最後の位置を保存し、重複があればその直後まで left をジャンプさせます。これにより、この典型問題を O(n) で解けます。✅
よくある質問
「重複のない最長部分文字列」レッスンは無料ですか？
はい。「重複のない最長部分文字列」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「重複のない最長部分文字列」で何を学びますか？
ウィンドウ内で最後に出現した位置を追跡します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「重複のない最長部分文字列」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。