Minimum amount of flips required to make binary strings match, under the restriction that there must never be three of the same bit consecutively

Question

Imagine you have two binary strings, a and b, given as input. a and b are both of the same length.
The objective is to find the minimum number of flips required to make a equal b, WITHOUT a ever having three of the same bit consecutively (e.g. 000 or 111 appearing anywhere in a is disallowed). Also, you may flip only one bit at a time. The input strings also never have three of the same bit appearing consecutively when they are given. b is immutable.

For example:
a = 0011
b = 0101

0011 -> 0010 -> 0110 -> 0100 -> 0101 (output: 4)

You could not go from 0011 to 0111, because then there would be three 1 bits in the string.

I'm not sure how to approach solving this problem, honestly. I think that a solution may involve dynamic programming, through.

Answer 1

well, i came back to this problem after a break and it wasn't actually hard. here's what i came up with:

function flip(c) {
    switch (c) {
        case "0": return "1";
        case "1": return "0";
        default: throw new Error("invalid character");
    }
}
function cloneFlip(str, idx) {
    let arr = str.split("");
    let c = arr[idx];
    arr[idx] = flip(c);
    return arr.join("");
}

function three(str) {
    for (let idx = 0; idx < str.length - 2; ++idx) {
        if (["000", "111"].includes(str.substring(idx, idx + 3))) {
            return true;
        }
    }
    return false;
}

function doStep(a, seen, currMut, queue/*, prev*/) {
    let length = a.length;

    for (let idx = 0; idx < length; ++idx) {
        let str = cloneFlip(a, idx);
        if (three(str)) {
            continue;
        }

        if (!seen.has(str)) {
            seen.add(str);
            queue.push([str, currMut]);
            /*let p = prev[str];
            if (!p || currMut - 1 < p.step) {
                prev[str] = { a, step: currMut - 1, };
            }*/
        }
    }

    return;
}

function go(a, b) {
    if (a.length != b.length) {
        throw new Error("length mismatch");
    }

    let queue = [];
    let seen = new Set(a);
    doStep(a, seen, 1, queue);

    let arr = [];
    while (queue.length) {
        let [str, muts] = queue.shift();
        if (str === b) {
            return muts;
        }
        doStep(str, seen, muts + 1, queue);
    }

    throw new Error("unreachable");
}