【ITニュース解説】🗓 Daily LeetCode Progress – Day 19

この解説では、LeetCodeというプログラミング問題を解くプラットフォームで取り上げられた2つの問題、「Max Consecutive Ones III」と「Find All Anagrams in a String」について、システムエンジニアを目指す初心者にも理解しやすいように解説する。両方の問題は「スライディングウィンドウ」というアルゴリズムのテクニックを使って効率的に解くことができる。

まず、「Max Consecutive Ones III」について説明する。この問題は、与えられた整数の配列（nums）の中で、最大でk個の0を1に置き換えることができる場合に、連続する1の最大長を求めるものだ。例えば、nums = [1,1,1,0,0,0,1,1,1,1,0]、k = 2の場合、0を2つまで1に置き換えることができるので、最長の連続する1の長さは6となる。

この問題を解くために、スライディングウィンドウを使う。スライディングウィンドウとは、配列の一部分を指し示す「窓」のようなもので、この窓を配列上で滑らせるように移動させながら処理を行うテクニックだ。ここでは、leftとrightという2つのポインタを使って窓の範囲を管理する。rightポインタを右方向に移動させながら窓を広げ、窓の中にある0の数がkを超えたら、leftポインタを右方向に移動させて窓を縮める。常に窓の中にある0の数がk以下になるように調整することで、条件を満たす最長の連続する1の長さを効率的に見つけ出すことができる。

具体的なコードを見てみよう。PythonとC++で解答例が示されているが、基本的な考え方は同じだ。まず、left、right、temp_k（置き換え可能な0の残り数）、max_temp（最長の連続する1の長さ）を初期化する。rightポインタを配列の最後まで移動させながら、以下の処理を行う。もしnums[right]が0であれば、temp_kを1減らす。もしtemp_kが0より小さくなったら（つまり、置き換え可能な0の数を超えてしまったら）、leftポインタを右方向に移動させ、nums[left]が0であればtemp_kを1増やす。そして、max_tempを、現在の窓の長さ（right - left + 1）と今までのmax_tempの値の大きい方で更新する。最終的にmax_tempが答えとなる。

次に、「Find All Anagrams in a String」について説明する。この問題は、与えられた文字列sの中で、別の文字列pのアナグラム（文字の並び替え）となる部分文字列の開始インデックスをすべて見つけるものだ。例えば、s = "cbaebabacd"、p = "abc"の場合、sの中でpのアナグラムとなるのは、"cba"（インデックス0から始まる）と"bac"（インデックス6から始まる）なので、答えは[0, 6]となる。

この問題もスライディングウィンドウを使って解くことができる。まず、文字列pの各文字の出現回数をカウントする。次に、文字列s上で長さがpと同じスライディングウィンドウを作り、その中の文字の出現回数をカウントする。そして、この2つのカウントが一致するかどうかを比較する。もし一致すれば、それはpのアナグラムなので、その開始インデックスを結果に追加する。スライディングウィンドウを右に1文字ずつ移動させながら、この処理を繰り返す。

コードを見ると、PythonではCounterという便利なクラスを使って文字の出現回数をカウントしている。C++では、長さ26の配列を使って各アルファベットの出現回数をカウントしている。どちらの言語でも、ウィンドウを移動させる際に、新しく追加された文字のカウントを増やし、削除された文字のカウントを減らすことで、効率的にカウントを更新している。そして、ウィンドウ内の文字のカウントとpの文字のカウントが一致するかどうかを比較し、一致すれば開始インデックスを結果に追加する。

両方の問題は、スライディングウィンドウの基本的な考え方（窓を広げたり縮めたりしながら条件を満たす範囲を見つける）を理解していれば、比較的簡単に解くことができる。重要なのは、問題を理解し、適切な窓のサイズや移動方法を考えることだ。また、コードを書く際には、各変数の役割や動きをしっかりと把握し、デバッグしやすいように心がけることが重要だ。

これらの問題を通して、スライディングウィンドウのテクニックを習得することで、様々な配列や文字列の問題を効率的に解くことができるようになる。