Building H2O

アルゴリズム概要

問題の説明

2種類のスレッド（oxygen と hydrogen）を同期させ、H2O分子を形成します。各分子は 水素2つ + 酸素1つ の3スレッドで構成され、次のグループが形成される前に必ず1グループが完了しなければなりません。

入出力例

Input: water = "HOH"
Output: "HHO"
説明: "HOH" や "OHH" も正解

Input: water = "OOHHHH"
Output: "HHOHHO"
説明: 順序は不定だが、必ず3文字単位(2H+1O)でグループ化

制約条件

• 3 * n == water.length
• 1 <= n <= 20 (最大60スレッド)
• 水素は必ず酸素の2倍存在

戦略

Semaphore + Barrier を組み合わせたマルチスレッド同期を実装します。

• h_sem (Semaphore): 水素スレッドの入場制御（初期値2 → 2つまで同時入場）
• o_sem (Semaphore): 酸素への通知用（初期値0 → 水素が通知）
• barrier (Barrier): 3スレッドの同期バリア

主要ポイント

• 時間計算量: O(1) per thread operation
• 空間計算量: O(1) - 固定サイズの同期オブジェクトのみ
• デッドロック回避: Barrierによる3スレッド同期 + セマフォチェーン

ステップバイステップ解説

Python実装

from __future__ import annotations
from typing import Callable
from threading import Semaphore, Barrier


class H2O:
    """
    H2O分子形成の同期制御

    Time Complexity: O(1) per thread
    Space Complexity: O(1)

    LeetCode実績: Runtime 45-55ms, Memory 20.2-20.4MB
    """

    def __init__(self) -> None:
        """
        同期機構の初期化

        - h_sem: 水素入場制御(初期値2 → 2つまで同時入場)
        - o_sem: 酸素通知用(初期値0 → 水素が通知)
        - barrier: 3スレッド同期バリア
        """
        # 水素入場制御: 2つまで許可
        self.h_sem: Semaphore = Semaphore(2)
        # 酸素待機: 水素が通知するまで0
        self.o_sem: Semaphore = Semaphore(0)
        # 3スレッド同期バリア
        self.barrier: Barrier = Barrier(3)

    def hydrogen(self, releaseHydrogen: Callable[[], None]) -> None:
        """
        水素スレッドの同期処理

        Args:
            releaseHydrogen: "H"を出力するコールバック

        処理フロー:
        1. h_sem取得(2つまで入場)
        2. o_semリリース(酸素に到着通知)
        3. バリア待機(3つ揃うまで)
        4. 出力
        5. h_semリリース(次のグループ用)
        """
        # 入場制御: 最大2スレッドまで
        self.h_sem.acquire()

        # 酸素に到着を通知
        self.o_sem.release()

        # 3スレッド揃うまで待機
        self.barrier.wait()

        # 水素出力
        releaseHydrogen()

        # 次のグループ用にリリース
        self.h_sem.release()

    def oxygen(self, releaseOxygen: Callable[[], None]) -> None:
        """
        酸素スレッドの同期処理

        Args:
            releaseOxygen: "O"を出力するコールバック

        処理フロー:
        1. o_sem取得×2(水素2つの到着待ち)
        2. バリア待機(3つ揃うまで)
        3. 出力
        """
        # 水素2つの到着を待機
        self.o_sem.acquire()
        self.o_sem.acquire()

        # 3スレッド揃うまで待機
        self.barrier.wait()

        # 酸素出力
        releaseOxygen()

フローチャート

フローの説明：
1. スレッドが到着すると、種別（H or O）を判定
2. Hydrogen: h_semで入場制御 → o_semで酸素に通知 → Barrier待機 → 出力 → h_semリリース
3. Oxygen: o_sem取得×2で水素2つ待機 → Barrier待機 → 出力
4. Barrier: 3スレッド揃うまで全員ブロック、揃った瞬間に全員リリース
5. 完了: 各スレッドが出力後、次のグループが形成可能

計算量分析

時間計算量

空間計算量

最適化の比較