JavaScriptでバイナリ文字列を単調増加にするための最小反転回数を求める方法

単調増加文字列とは

'0'と'1'のみで構成される文字列が「単調増加」とみなされるのは、任意の個数（0個でも可）の'0'が先頭に並び、その後に任意の個数（これも0個でも可）の'1'が続く場合です。つまり、「000111」「0011」「1」などは単調増加ですが、「1100」「010」などは該当しません。

問題の概要

本記事では、バイナリ文字列 str を唯一の引数として受け取るJavaScript関数を作成します。

文字列内の任意の'0'を'1'へ、または任意の'1'を'0'へと反転（フリップ）することができます。このとき、文字列全体を単調増加にするために必要な最小の反転回数を求めて返すのが目標です。

入力例

const str = '00110';

出力例

const output = 1;

出力の解説

末尾の'0'を'1'に反転すると、文字列は「00111」となり、単調増加になります。他の反転パターンでは1回未満で達成できないため、答えは1となります。

実装例：メモ化再帰によるアプローチ

以下のコードでは、各インデックスと直前の文字の状態をキーとしたメモ化（キャッシュ）を用いた再帰的な動的計画法で、最小反転回数を効率的に求めています。

const str = '00110';
const countFlips = (str = '') => {
    const map = {}
    const helper = (index, prev) => {
        map[index] = map[index] || {}
        if (map[index][prev] !== undefined) {
            return map[index][prev]
        }
        if (index >= str.length) {
            return 0
        }
        if (prev === '0') {
            if (str[index] === '0') {
                map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1)
            } else {
                map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1)
            }
        } else if (str[index] === '0') {
            map[index][prev] = helper(index + 1, '1') + 1
        } else {
            map[index][prev] = helper(index + 1, '1')
        }
        return map[index][prev]
    }
    return helper(0, '0')
};
console.log(countFlips(str));

出力結果

1

アルゴリズムのポイント

• 再帰関数 helper： 現在のインデックスと、それまでの選択によって決まる「前の文字」（prev）を引数に取り、以降の文字列を単調増加にするのに必要な最小反転回数を返します。
• メモ化： オブジェクト map を使い、同じ状態（インデックス×前の文字）の計算結果をキャッシュすることで、指数時間の再帰を線形時間相当まで高速化しています。
• 遷移のロジック： prevが'0'の場合は、現在の文字をそのまま使うか反転するかの両方が可能なため Math.min で最小を選びます。prevが'1'になった後は'0'に戻せないため、強制的に'1'へ揃える分岐のみとなります。

この手法により、文字列の長さが長くなっても計算量を抑えながら正確に最小反転回数を導き出すことができます。