/*
Problem Statement: Maximum weight transformation of a given string
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 

This problem was asked during an interview in Adobe.

First I provided a DP based solution and then a brute force solution. 
*/

package algo.dp;

public class MaxWeightTransformation{
	
	/*
  Dynamic Programming Solution.
	str1[] : String array (str.toCharArray())
	i: first index of string (0)
	size: str.length() -1
	lookup: int[str.length()] (initialize all lookup indexes with -1)
	*/	
	public int maxWeightTransformationDPSol(char str1[], int i, int size, int lookup[])
		{
		// If the counter has gone past maximum size 
		// of string, then return 0
		if (i > size)
			return 0;
		// If the counter is equal to the size of 
		// string, then retun 1. Since, there is no point of string
		// transformation.
		if (i == size)
			return 1;
	
		// if the subproblem is already solved
		if (lookup[i] != -1)
			return lookup[i];
		
		// If pair is not made, weight gained is 1
		int res = 1 + max_len(str1, i+1, size, lookup);
		
		// is pair is made
		if(i+1 <= size)
		{
			// if consecutive elements are same
			// weight gained is 3 after transformation
			if (str1[i] == str1[i+1])
				{
				res = Math.max(res, 3 + max_len(str1, i+2, size, lookup));
				}
			// if consecutive elements are different
			// weight gained is 4
			else if(str1[i] != str1[i+1])
				{
				res = Math.max(res, 4 + max_len(str1, i+2, size, lookup));
				}
		}
		return lookup[i] = res;
		}
		
	/*
  Brute Force Solution  
	str1[] : String array (str.toCharArray())
	i: first index of string (0)
	size: str.length() -1
	*/	
	public int maxWeightTransformationNoDPSol(char str1[], int i, int size)
		{
		// If the counter has gone past maximum size 
		// of string, then return 0
		if (i > size)
			return 0;
		
		// If the counter is equal to the size of 
		// string, then retun 1. Since, there is no point of string
		// transformation.
		if (i == size)
			return 1;
	
		// If pair is not made, weight gained is 1
		int res = 1 + max_len(str1, i+1, size);
		
		// is pair is made
		if(i+1 <= size)
		{
			// if consecutive elements are same
			// weight gained is 3 after transformation
			if (str1[i] == str1[i+1])
				{
				res = Math.max(res, 3 + max_len(str1, i+2, size));
				}
			// if consecutive elements are different
			// weight gained is 4
			else if(str1[i] != str1[i+1])
				{
				res = Math.max(res, 4 + max_len(str1, i+2, size));
				}
		}

		return res;
		}
	
	
	}


@@ -1573,36 +1573,57 @@
 nt res = 1 + max
-_len
+WeightTransformationDPSol
 (str1, i+1, size
@@ -1822,36 +1822,57 @@
 max(res, 3 + max
-_len
+WeightTransformationDPSol
 (str1, i+2, size
@@ -2020,36 +2020,57 @@
 max(res, 4 + max
-_len
+WeightTransformationDPSol
 (str1, i+2, size
@@ -2661,28 +2661,51 @@
 es = 1 + max
-_len
+WeightTransformationNoDPSol
 (str1, i+1, 
@@ -2904,28 +2904,51 @@
 res, 3 + max
-_len
+WeightTransformationNoDPSol
 (str1, i+2, 
@@ -3104,12 +3104,35 @@
  max
-_len
+WeightTransformationNoDPSol
 (str

Update MaxWeightTransformation.java