Maximum Weight Transformation of String

Problem Overview

Each character is worth 1 if it is left as a single.

Intuition

Each character is worth 1 if it is left as a single. Two neighbors can be taken as a pair instead. A pair of different letters is already alternating, so it is worth 4, which is 2 more than the two singles. A pair of equal letters needs one toggle to become alternating, so it is worth 4 minus that toggle, which is 3, only 1 more than the two singles. Pairs cannot share a character. Choosing the best set of these bonuses is the same recurrence as the house robber problem: at each boundary, skip the pair or take it and skip the previous boundary. Only the previous two answers are required, and the final weight is the length plus the best bonus.

Algorithm

1Start both previous answers at 0.
2Walk each boundary between neighbors. The bonus is 2 when the letters differ and 1 when they match.
3The new answer is the larger of skipping this boundary and taking its bonus on top of the answer from two steps back.
4Shift the two saved answers forward.
5Return the length plus the latest answer. An empty string returns 0 and a single character returns 1.

Example Walkthrough

Input: s = "ABB"

1. The first boundary is A and B, which differ, so the bonus is 2. The best bonus so far is 2.
2. The next boundary is B and B, which match, so the bonus is 1. Taking it would replace the earlier bonus of 2, so the best bonus stays 2.
3. Three characters plus a bonus of 2 is 5. That is the pair AB worth 4, plus the leftover B worth 1.

Output: 5

Common Pitfalls

• Equal letters are still worth pairing. After one toggle the pair is worth 3, which beats two singles worth 2.
• Adjacent pairs overlap. Taking both boundaries that touch the same character counts that character twice.
• The bonus is added on top of the length. Returning only the bonus drops the value of every single character.
• An empty string has length 0 and no boundary, so the weight is 0.

Maximum Weight Transformation of String.java

Java

// Approach: Every character is worth 1 by itself. Pairing two neighbors adds
// 2 more when they already differ, and 1 more when one of them must be
// toggled. Pairs cannot share a character, so the best set of bonuses is the
// house-robber recurrence and only the previous two answers are kept.
// Complexity: O(n) time, O(1) extra space.
class Solution {
    public int getMaxWeight(String s) {
        int n = s.length();
        int prev2 = 0;
        int prev1 = 0;
        for (int i = 1; i < n; i++) {
            int gain = s.charAt(i - 1) == s.charAt(i) ? 1 : 2;
            int cur = Math.max(prev1, prev2 + gain);
            prev2 = prev1;
            prev1 = cur;
        }
        return n + prev1;
    }
}

Was this solution helpful?