Reducing a Binary Number to One

Given a binary string representing a positive integer, the objective is to reduce this number to 1 using the minimum number of steps. The operations allowed are:

• If the current number is even, divide it by 2.
• If the current number is odd, add 1 to it.

Since the input length can be up to 500, converting the binary string to an integer using standard types might lead to overflow in languages like JavaScript or C++. Therefore, it is safer to simulate the operations directly on the binary string or array.

Algorithm Approach:

1. Simulate the process using an array of characters.
2. While the array represents a number greater than 1:
   • If the last digit is '0', the number is even. Remove the last digit (equivalent to right-shift or division by 2).
   • If the last digit is '1', the number is odd. Add 1 to the binary number. This involves carrying over: iterate from the end, turning '1's to '0's until a '0' is found and turned into '1'. If all digits are '1', prepend a '1'.
3. Increment the step count for each operation.

/**
 * @param {string} s
 * @return {number}
 */
var minStepsBinary = function(s) {
    let digits = s.split('');
    let steps = 0;

    while (digits.length > 1) {
        if (digits[digits.length - 1] === '0') {
            // Even: divide by 2 (right shift)
            digits.pop();
        } else {
            // Odd: add 1 (handle carry)
            let i = digits.length - 1;
            while (i >= 0 && digits[i] === '1') {
                digits[i] = '0';
                i--;
            }
            if (i >= 0) {
                digits[i] = '1';
            } else {
                digits.unshift('1');
            }
        }
        steps++;
    }
    return steps;
};

Constructing the Longest Happy String

A string is considered "happy" if it does not contain any substring of length 3 consisting of the same character (e.g., "aaa" or "bbb"). Given counts a, b, and c for characters 'a', 'b', and 'c' respectively, the task is to construct the longest possible happy string.

Greedy Strategy:

1. Always prioritize the character with the highest remaining count.
2. Before appending a character, check if it would create a sequence of three identical characters.
3. If the most frequent character cannot be used (because it would violate the rule), use the character with the second-highest count.
4. If no characters can be appended without violating the rules, the process terminates.

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}
 */
var longestDiverseString = function(a, b, c) {
    let chars = [
        { char: 'a', count: a },
        { char: 'b', count: b },
        { char: 'c', count: c }
    ];
    let result = '';

    while (true) {
        // Sort by count descending to always try the most frequent char first
        chars.sort((x, y) => y.count - x.count);

        let added = false;
        for (let item of chars) {
            if (item.count === 0) continue;

            // Check if appending this char would create 'xxx'
            let len = result.length;
            if (len >= 2 && result[len - 1] === item.char && result[len - 2] === item.char) {
                continue; // Skip this character as it would violate the rule
            }

            result += item.char;
            item.count--;
            added = true;
            break; // Restart loop to re-evaluate priorities
        }

        if (!added) break;
    }
    return result;
};

Stone Game III

In this game, Alice and Bob take turns picking stones from a row. On each turn, a player can take 1, 2, or 3 stones from the left end. Each stone has a value (positive or negative). The player with the highest total value wins. The goal is to determine the winner assuming both play optimally.

Dynamic Programming Approach:

Let dp[i] represent the maximum relative score the current player can achieve starting from index i to the end, assuming optimal play. The relative score is defined as (current player's score) - (opponent's score).

1. Iterate backwards from the last stone to the first.
2. At index i, the player can choose to take stones from i to j (where j ranges from i to i+2).
3. The score obtained is the sum of values from i to j minus the best score the opponent can get from the remaining stones (dp[j+1]).
4. The state transition is: dp[i] = max(sum(values[i..j]) - dp[j+1]) for all valid j.

/**
 * @param {number[]} stoneValue
 * @return {string}
 */
var stoneGameIII = function(stoneValue) {
    const n = stoneValue.length;
    // dp[i] represents the max net score (Alice - Bob) starting from index i
    const dp = new Array(n + 1).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        let maxNetScore = -Infinity;
        let currentSum = 0;

        // Try taking 1, 2, or 3 stones
        for (let j = i; j < Math.min(i + 3, n); j++) {
            currentSum += stoneValue[j];
            // Current score minus opponent's best subsequent score
            let score = currentSum - dp[j + 1];
            maxNetScore = Math.max(maxNetScore, score);
        }
        dp[i] = maxNetScore;
    }

    if (dp[0] > 0) return "Alice";
    if (dp[0] < 0) return "Bob";
    return "Tie";
};