非固定長スライディングウィンドウのテンプレート
public int variableWindow(int[] nums) {
Map<Integer, Integer> state = new HashMap<>(); // 適切なデータ構造を選択
int start = 0;
int maxLen = 0;
for (int end = 0; end < nums.length; end++) {
// ウィンドウを拡大
// nums[end] を state に O(1) で追加
while (/* ウィンドウが無効な間 */) {
// ウィンドウが有効になるまで収縮
// nums[start] を state から O(1) で削除
start++;
}
// ここでは現在のウィンドウの状態は有効（不変条件）
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}
固定長スライディングウィンドウのテンプレートとJava実装
固定長ウィンドウはスライディングウィンドウアルゴリズムの中で最も基本的で理解しやすい型です。ウィンドウサイズは固定であり、解法は高い一貫性を持っています。
1. 核心思想と解法の流れ
1.1 核心思想
固定長ウィンドウの核心は「ウィンドウをスライドさせる際、左端の要素を除去し、右端の要素を追加する」ことで、毎回ウィンドウ全体を再構築する必要がなく、計算量を O(n*k) から O(n) に改善します。
1.2 汎用解法（4ステップ）
- 初期化：結果変数、ウィンドウ内の統計変数、左端インデックス
left = 0を定義。 - 最初のウィンドウを構築：先頭
k個の要素をウィンドウに取り込み、統計変数を更新。 - 初期結果を記録：最初のウィンドウの統計値を結果変数に代入。
- 残りの要素をスライド走査：
- 左端要素を除去し
left++； - 右端要素を追加；
- 結果を更新。
- 左端要素を除去し
- 最終結果を返す。
2. Java汎用テンプレート（配列の固定長ウィンドウ和）
/**
* 固定長スライディングウィンドウの汎用テンプレート（配列版）
* 例：長さ k の部分配列の最大和を求める
* @param nums 入力配列
* @param k ウィンドウの固定長
* @return 最適な結果（ここでは最大和）
*/
public static int fixedWindowTemplate(int[] nums, int k) {
// 1. 境界チェック
if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
return 0;
}
int n = nums.length;
int winSum = 0; // ウィンドウ内の要素和
int left = 0; // 左端
int maxSum = 0; // 結果：最大和
// 2. 最初のウィンドウ（先頭k個）
for (int i = 0; i < k; i++) {
winSum += nums[i];
}
// 3. 初期結果
maxSum = winSum;
// 4. スライド走査
for (int right = k; right < n; right++) {
// 左端除去
winSum -= nums[left++];
// 右端追加
winSum += nums[right];
// 結果更新
maxSum = Math.max(maxSum, winSum);
}
// 5. 結果を返す
return maxSum;
}
3. 実戦例題（2つの頻出シナリオ）
シナリオ1：長さkの部分配列の最大和
問題
整数配列 nums と整数 k が与えられたとき、長さ k の連続部分配列の最大和を求めよ。
Java実装
public class FixedWindowArray {
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
System.out.println("最大和：" + maxSubarraySum(nums, k));
}
public static int maxSubarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
throw new IllegalArgumentException("入力が無効です");
}
int winSum = 0;
int left = 0;
int maxSum = Integer.MIN_VALUE;
// 最初のウィンドウ
for (int i = 0; i < k; i++) {
winSum += nums[i];
}
maxSum = winSum;
// スライド
for (int right = k; right < nums.length; right++) {
winSum -= nums[left++];
winSum += nums[right];
maxSum = Math.max(maxSum, winSum);
}
return maxSum;
}
}
実行結果
最大和：16
シナリオ2：長さkの重複文字なし部分文字列
問題
文字列 s と整数 k が与えられたとき、長さ k で重複文字を含まないすべての部分文字列をリストとして返せ。
Java実装
import java.util.*;
public class FixedWindowString {
public static void main(String[] args) {
String s = "abcabcbb";
int k = 3;
List<String> result = findUniqueSubstrings(s, k);
System.out.println("結果：" + result);
}
public static List<String> findUniqueSubstrings(String s, int k) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0 || k <= 0 || k > s.length()) return res;
int n = s.length();
int left = 0;
Set<Character> windowChars = new HashSet<>();
// 最初のウィンドウ
for (int i = 0; i < k; i++) {
windowChars.add(s.charAt(i));
}
if (windowChars.size() == k) {
res.add(s.substring(left, left + k));
}
// スライド
for (int right = k; right < n; right++) {
char leftChar = s.charAt(left);
windowChars.remove(leftChar);
left++;
char rightChar = s.charAt(right);
windowChars.add(rightChar);
if (windowChars.size() == k) {
res.add(s.substring(left, left + k));
}
}
return res;
}
}
実行結果
結果：[abc, bca, cab]
Longest Repeating Character Replacement 問題解説
1. 問題の核心（LeetCode 424）
文字列 s と整数 k が与えられます。最大 k 文字を任意の大文字英字に置き換えることで、同じ文字からなる最長の部分文字列の長さを求めます。
例：s = "ABAB", k = 2 → 出力 4（ "AAAA" または "BBBB" ）
2. 解法の核心（非固定長スライディングウィンドウ + 貪欲法）
2.1 ウィンドウ有効性の公式
ウィンドウ長 - ウィンドウ内の最多出現文字数 ≤ k
maxCount：ウィンドウ内で最も多く出現する文字の出現回数- 差分が
k以下なら、最大k回の置き換えで統一可能
2.2 アルゴリズムの流れ
left = 0,maxLen = 0,maxCount = 0,counts[26]を初期化- 右端
rightを 0 から順に進める：- 現在の文字のカウントを増やし、
maxCountを更新 winLen - maxCount > kなら、左端を進めてウィンドウを縮小maxLenを更新
- 現在の文字のカウントを増やし、
- 最後に
maxLenを返す
注意：maxCount は縮小時に減らさない（貪欲な最適化）。
3. Java実装
public class LongestRepeatingCharReplacement {
public int characterReplacement(String s, int k) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int left = 0;
int maxLen = 0;
int maxCount = 0;
int[] cnt = new int[26]; // A-Z の出現回数
for (int right = 0; right < n; right++) {
int idx = s.charAt(right) - 'A';
cnt[idx]++;
maxCount = Math.max(maxCount, cnt[idx]);
// 有効性チェック：winLen - maxCount > k なら縮小
while (right - left + 1 - maxCount > k) {
cnt[s.charAt(left) - 'A']--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
public static void main(String[] args) {
LongestRepeatingCharReplacement sol = new LongestRepeatingCharReplacement();
System.out.println(sol.characterReplacement("ABAB", 2)); // 4
System.out.println(sol.characterReplacement("AABABBA", 1)); // 4
}
}
30. 全ての単語を連結した部分文字列
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
int wc = words.length; // 単語数
int wl = words[0].length(); // 単語長
int sl = s.length();
// 単語長でオフセットを変えながら n 回ループ
for (int off = 0; off < wl; off++) {
if (off + wc * wl > sl) break; // 残り文字数不足
// 差分マップ：キー＝単語、値＝ウィンドウ内出現数 - words内出現数
Map<String, Integer> diff = new HashMap<>();
// 最初のウィンドウを構築
for (int j = 0; j < wc; j++) {
String w = s.substring(off + j * wl, off + (j + 1) * wl);
diff.put(w, diff.getOrDefault(w, 0) + 1);
}
for (String w : words) {
diff.put(w, diff.getOrDefault(w, 0) - 1);
if (diff.get(w) == 0) diff.remove(w);
}
// スライド走査（単語単位で進む）
for (int start = off; start < sl - wc * wl + 1; start += wl) {
if (start != off) {
// 右側追加
String w = s.substring(start + (wc - 1) * wl, start + wc * wl);
diff.put(w, diff.getOrDefault(w, 0) + 1);
if (diff.get(w) == 0) diff.remove(w);
// 左側削除
w = s.substring(start - wl, start);
diff.put(w, diff.getOrDefault(w, 0) - 1);
if (diff.get(w) == 0) diff.remove(w);
}
if (diff.isEmpty()) {
res.add(start);
}
}
}
return res;
}
}
このコードは「単語の配列 words の全ての単語を一度ずつ連結して得られる部分文字列」を s から探す問題を解いています。差分マップ diff を使うことで、毎回ウィンドウ全体をチェックせずに O(n) で動作します。
- 外側ループ：単語長
wlでオフセットを変え、すべての開始位置をカバー。 - 初期ウィンドウ：最初の
wc個の単語をdiffに加え、wordsの出現を差し引く。 - スライド：左単語を削除、右単語を追加して
diffを更新。空なら一致。