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.
Read full article from 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).
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// transformationint 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);}