Maximum weight transformation of a given string

Problem Statement

The maximum weight transformation of a given string problem states that given a string consisting only of two characters ‘A’ and ‘B’. We have an operation where we can transform string to another string by toggling any character. Thus many transformations are possible. Out of all the possible transformations, find out the weight of the maximum weight transformation.

Algorithm

Weight of string = weight of total pairs + weight of single characters - total number of toggles.
Two different consecutive characters are considered as pairs.
Weight of single pair (both characters are different) = 2
Weight of single character = 1
(These values are just some random values and can be taken as input)

Example

BA

2

Explanation:

There are four possibilities for string “AA”, to transform into which are the following:

AB → 2 – 1 = 1

BA → 2 – 1 = 1

AA → 2

BB → 2

Since all these transformations weigh the same, we can choose one of the any possible transformations.

BAA

3

Explanation: There are a total of 8 transformations, out of which transformations having one pair and one single character has a maximum value.

Approach for maximum weight transformation of a given string

Naive Approach

We make all the possible transformations by toggling each character. After making all transformations we find the value of each transformation and then find the maximum value by calculating the value of each transformation.

Efficient Approach

We will use recursion to find the maximum weight transformation of a given string, by using pruning to reduce the calculations. If we have the current character and second character different, that is this is a pair. In this case, we have two options either we change the first character and move ahead or we don’t toggle the characters and move ahead. The other condition would be when we have current character and second characters the same. In this case, we will toggle the character and make it a pair, or we don’t and move ahead.

Since the initial (or original) problem can be converted into smaller subproblems, we will use dynamic programming to store the subproblems and use them further.

Code

C++ Code for maximum weight transformation of a given string problem

#include<bits/stdc++.h>
using namespace std;

int pairCost, toggleCost;

int maxWeightOfTransformation(string s, vector<int> &dp, int i, int stringLength){
    //base case
    if(i>=stringLength)
        return 0;
    if(dp[i]!=-1)
        return dp[i];

    // consider current character as a single character(not a pair)
    int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
    if(i+1<stringLength){
        if(s[i]!=s[i+1])
            answer = max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        else
            answer = max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
    }
    return dp[i] = answer;
}

int main()
{
    string s;cin>>s;
    cout<<"Enter pairCost and toggleCost"<<endl;
    cin>>pairCost>>toggleCost;
    int stringLength = s.size();
    vector<int> dp(stringLength, -1);
    cout << "Maximum weight of a transformation of "<<s<<" is " <<maxWeightOfTransformation(s, dp, 0, stringLength);
    return 0;
}

AB
Enter pairCost and toggleCost
2 1

Maximum weight of a transformation of AB is 2

Java Code for maximum weight transformation of a given string

import java.util.*;

class Main{
    static int pairCost, toggleCost;
    
    static int maxWeightOfTransformation(String s, int[] dp, int i, int stringLength){
        //base case
        if(i>=stringLength)
            return 0;
        if(dp[i]!=-1)
            return dp[i];
    
        // consider current character as a single character(not a pair)
        int answer = 1 + maxWeightOfTransformation(s, dp, i+1, stringLength);
        if(i+1<stringLength){
            if(s.charAt(i)!=s.charAt(i+1))
                answer = Math.max(pairCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
            else
                answer = Math.max(pairCost-toggleCost + maxWeightOfTransformation(s, dp, i+2, stringLength), answer);
        }
        return dp[i] = answer;
    }
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println("Enter pairCost and toggleCost");
        pairCost=sc.nextInt();
        toggleCost=sc.nextInt();
        int stringLength = s.length();
        int dp[] = new int[stringLength];
        for(int i = 0;i<stringLength;i++)dp[i]=-1;
        int answer = maxWeightOfTransformation(s, dp, 0, stringLength);
        System.out.println("Maximum weight of a transformation of "+s+" is "+answer);
    }
}

AB 
Enter pairCost and toggleCost 
2 1

Maximum weight of a transformation of AB is 2

Complexity Analysis

Time Complexity: O(N)

Since we have used an algorithm that is using a 1D DP, and the transition among the states is also O(1). This makes the algorithm run in O(N) total time complexity.

Space Complexity: O(N)

Here we have used 1D array for DP, thus the algorithm has O(N) space complexity.