Maximum weight transformation of a given string - GeeksforGeeks

Maximum weight transformation of a given string - GeeksforGeeks
Given a string consisting of only A's and B's. We can transform the given string to another string by toggling any character. Thus many transformations of the given string are possible. The task is to find Weight of the maximum weight transformation.
Weight of a sting is calculated using below formula.

Weight of string = Weight of total pairs + 
                   weight of single characters - 
                   Total number of toggles.

Two consecutive characters are considered as pair only if they 
are different. 
Weight of a single pair (both character are different) = 4
Weight of a single character = 1 

[Adobe Online Round]
You are given string consisting of only A's and B's. You can toggle a character from A to B and vice versa. Also, you can pair two adjacent elements if you wish but the pair must contain dissimilar characters i.e. the pair should be AB or BA. Thus many transformations of the given string is possible. So, you need to find the weight of string with maximum weight. Weight of a pair is 4 and weight of a single character is 1. Weight of the complete string is calculated as following. 
Weight of string = weight of total pairs + weight of single characters - total number of toggles (in formation of this string).

Let the string be ABB so transformations possible are "ABB", "ABA", "AAB", "AAA", "BBB", "BBA", "BAB", "BAA"} with respective weight {5,4,4,1,2,3,3,2}. Maximum weight is found 5 in string 1.

// Returns wieght of the maximum weight

// transformation

int getMaxRec(string &str, int i, int n, int lookup[])

{

    // Base case

    if (i >= n) return 0;

 

    //If this subproblem is already solved

    if (lookup[i] != -1) return lookup[i];

 

    // Don't make pair, so weight gained is 1

    int ans = 1 + getMaxRec(str, i+1, n, lookup);

 

    // If we can make pair

    if (i+1 < n)

    {

      // If elements are dissmilar, weight gained is 4

      if (str[i] != str[i+1])

        ans = max(4 + getMaxRec(str, i+2, n, lookup),

                  ans);

 

      // if elements are similar so for making a pair

      // we toggle any of them. Since toggle cost is

      // 1 so overall weight gain becomes 3

      else ans = max(3 + getMaxRec(str, i+2, n, lookup),

                    ans);

    }

 

    // save and return maximum of above cases

    return lookup[i] = ans;

}

 

// Initializes lookup table and calls getMaxRec()

int getMaxWeight(string str)

{

    int n = str.length();

 

    // Create and initialize lookup table

    int lookup[n];

    memset(lookup, -1, sizeof lookup);

 

    // Call recursive function

    return getMaxRec(str, 0, str.length(), lookup);

}

Read full article from Maximum weight transformation of a given string - GeeksforGeeks