通过交换相邻字符将字符串 S 转换为 T 并求得最大点数
在本题中，我们将根据问题陈述中的条件，在将字符串 S 转换为 T 的过程中，求得最大点数。
我们可以遍历字符串 S，并通过最大交换使字符串 S 中的每个字符与字符串 T 中同一索引处的字符相同，从而获得最大点数。
另一种方法，我们将根据对字符串的观察，编写一个数学公式来得出答案。
问题陈述 - 我们给出了一个包含字母和数字字符的字符串 S 和 T。我们需要在将字符串 S 转换为 T 时计算最大点数。
为了得到 ($\mathrm{S_{p}-s_{p}+1}$) 个点，我们需要交换字符串 S 中的 $\mathrm{S_{p}}$ 和 $\mathrm{S_{p}+1}$ 元素。
示例
输入
S = "543"; T = "345";
输出
4
解释
首先，交换 (4, 3) 得到 1 分，字符串变为 534。
接下来，交换 (5, 3) 得到 2 分，字符串变为 354。
最后一步，交换 (5, 4) 得到 1 分，字符串变为与 T 相同的结果。
输入
S = "1234"; T = "1234";
输出
0
解释 - 两个字符串已经相同，因此得 0 分。
输入
S = "179"; T = "125";
输出
-1
解释 - 无论如何，我们无法通过交换字符将字符串 S 转换为 T。因此，它会打印 -1。
方法 1
在此方法中，如果两个字符串的第 p 个索引处的字符不匹配，我们会在字符串 S 中找到匹配字符的下一个索引。之后，我们将匹配字符与字符串中的字符交换，将其放置在第 p 个索引处，并将获得的点数相加。这样，我们替换字符串 S 中每个不匹配的字符，并计算它们的点数之和。
算法
步骤 1 - 将 'pnt' 初始化为 0，以存储最大点数。
步骤 2 - 开始遍历字符串。
步骤 3 - 如果字符串 S 和 T 中第 p 个索引处的字符相同，则进入下一次迭代。
步骤 4 - 否则，在字符串 S 中找到 T[p] 的下一个索引。如果没有找到字符，则返回 -1，因为我们无法将字符串 S 转换为 T。
步骤 5 - 使用 while 循环进行迭代，直到 q > p 交换字符串字符。
步骤 6 - 将 S[q - 1] - S[q] 的值添加到 'pnt' 值中，该值因 S[q - 1] 和 S[q] 字符交换而获得一分。
步骤 7 - 使用 swap() 方法交换 S[q - 1] 和 S[q] 字符。同时，将 q 的值减 1。
步骤 8 - 返回 'pnt' 值。
示例
#include <iostream>
using namespace std;
int getMaximumPoint(string S, string T, int str_len) {
int pnt = 0;
for (int p = 0; p < str_len; p++) {
// 当同一索引处的字符相同时
if (S[p] == T[p]) {
continue;
}
int q = p + 1;
// 查找下一个匹配字符的索引
while (q < str_len && S[q] != T[p]){
q++;
}
// 如果没有找到匹配的字符
if (q == str_len){
return -1;
}
// 交换角色并获得积分
while (q > p) {
pnt += S[q - 1] - S[q];
swap(S[q], S[q - 1]);
q--;
}
}
//返回总分
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "将字符串 S 转换为 T 时我们可以得到的最大 pnt 是 "
<<getMaximumPoint(S, T, str_len) << endl;
return 0;
}
输出
将字符串 S 转换为 T 时我们可以得到的最大 pnt 是 4
时间复杂度 - O(N*N) 遍历字符串并找到下一个匹配字符的索引。
空间复杂度 - O(1)，因为我们不使用任何额外空间。
方法 2
在这种方法中，我们将创建一个公式来获取问题的输出。
当我们交换 $\mathrm{S_{p}}$ 和 $\mathrm{S_{p}+1}$ 个字符时，我们得到的点等于 ($\mathrm{S_{p}+1-s_{p}}$)。
假设字符的初始位置为 p，交换后，字符的位置为 q。
每当我们交换 $\mathrm{S_{p} + 1}$ 和 $\mathrm{S_{p}}$，成本增加 ($\mathrm{S_{p}+1-s_{p}}$)。这里，每次交换 q 都会增加 1。
这里，我们可以说，每当 q 增加 1，积分就会增加 Sp;每当 q 减少 1，积分就会减少 $\mathrm{S_{p}}$。
因此，单个字符的最终成本为 $\mathrm{S_{p}(q - p)}$。
这里，$\mathrm{S_{p} * q}$ 等于 $\mathrm{T_{p} * p}$，因为我们令字符串 S 等于 T。
因此，单个字符的成本为 $\mathrm{T_{p} * p - S_{p} * p}$，其中 'p' 是特定索引。
以下是获取输出的最终公式。
Sum($\mathrm{T_{p} * p - S_{p} * p}$)，其中 1 <= p <= 字符串长度
算法
步骤 1 - 开始遍历字符串。
步骤 2 - 将字符值与其在 T 和 S 字符串中的索引相乘，并从 S 中减去 T 的值。然后将结果值添加到 'pnt' 变量中。
步骤 3 - 返回 'pnt' 值。
示例
#include <iostream>
using namespace std;
long getMaximumPoint(string S, string T, int str_len) {
//存储每个数字与其索引相乘的和
int pnt = 0;
for (int p = 0; p < str_len; p++) {
pnt += (T[p] - '0') * 1l * (p + 1) - (S[p] - '0') * 1l * (p + 1);
}
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "将字符串 S 转换为 T 时我们可以得到的最大 pnt 是 "
<< getMaximumPoint(S, T, str_len) << endl;
return 0;
}
输出
将字符串 S 转换为 T 时我们可以得到的最大 pnt 是 4
时间复杂度 - O(N) 遍历字符串。
空间复杂度 - O(1)，因为我们不使用任何动态空间。
在第二种方法中，我们根据观察结果创建了解决问题的公式。它也适用于多次包含相同字符的字符串，因为每次出现一个元素时，我们都会交换另一个元素，成本保持不变。
