# 特定の文字列の最大重み変換

よく聞かれる Amazon (アマゾン） ブラックロック ByteDance コードネーション DEショウ エクスペディア JPモルガン オラキャブ

## アルゴリズム

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)

## 例

BA
2

AB→2– 1 = 1

BA→2– 1 = 1

AA→2

BB→2

これらの変換はすべて同じ重みであるため、可能な変換のXNUMXつを選択できます。

BAA
3

## コード

### 与えられた文字列問題の最大の重み変換のためのC ++コード

#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])
else
}
}

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コード

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))
else
}
}

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

## 複雑さの分析

### 時間の複雑さ： オン）

1D DPを使用するアルゴリズムを使用しているため、状態間の遷移もO（1）です。 これにより、アルゴリズムはO（N）の合計時間計算量で実行されます。

### スペースの複雑さ： オン）

ここでは、DPに1D配列を使用しているため、アルゴリズムにはO（N）空間の複雑さがあります。