字符串旋转后首尾字符的最大乘积

---

在这个问题中，我们将通过多次旋转字符串来找到字符串首尾字符可能的最大乘积。

朴素的方法是找到字符串的所有旋转，取首尾字符的乘积，并选择最大乘积作为答案。

另一种方法是找到每个相邻字符对的乘积，并选择最大乘积。

问题陈述 - 我们给定一个包含数字字符的字符串 num。我们需要找到给定字符串多次左旋转或右旋转后首尾字符的最大乘积。

示例

输入

num = "9834546";

输出

72

解释 - 我们可以将字符串左旋转 1 次。因此，字符串变为 8345469，如果我们取首尾字符的乘积，则得到 72。

输入

num = "235467";

输出

42

解释 - 如果我们进行 1 次右旋转，则字符串变为 723546。因此，第一个字符是 7，最后一个字符是 6。两者的乘积为 42。

输入

num = "11278654";

输出

56

解释 - 给定字符串的一次旋转是 78654112。因此，首尾字符的乘积为 56。

方法 1

在这种方法中，我们将对字符串进行总共 N 次左旋转。之后，我们将取当前旋转的首尾字符的乘积，并跟踪每次旋转的最大乘积。

算法

步骤 1 - 使用字符串长度初始化 'len' 变量，使用原始字符串的首字符初始化 'first' 变量，使用原始字符串的尾字符初始化 'last' 变量。同时，使用首尾字符的乘积初始化 'maximum'。

步骤 2 - 开始遍历 'num' 字符串。

步骤 3 - 使用 substr() 方法将子字符串左旋转。

步骤 4 - 获取当前旋转的首尾数字值。

步骤 5 - 如果首尾字符的乘积大于 'maximum' 的值，则更新 'maximum' 的值。

步骤 6 - 返回 'maximum' 的值。

示例

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

int getMaxProduct(string num) {
    int len = num.size();
    int first = num[0] - '0';
    int last = num[len - 1] - '0';
    // Get the product of the first and last character of the original string
    int maximum = first * last;
    // Rotate string by p rotations
    for (int p = 0; p < num.size() - 1; p++) {
        // Make left rotation by 1 unit using the substr() method
        num = num.substr(1) + num[0];
        first = num[0] - '0';
        last = num[len - 1] - '0';
        maximum = max(maximum, first * last);
    }
    return maximum;
}
int main() {
    string num = "9834546";
    cout << "The maximum product of the first and last character after rotation is - " << getMaxProduct(num);
    return 0;
}

输出

The maximum product of the first and last character after rotation is − 72

时间复杂度 - 对给定字符串进行总共 N 次旋转，时间复杂度为 O(N*N)。

空间复杂度 - O(1)，因为我们没有使用额外的空间。

方法 2

在这种方法中，我们将取给定字符串中相邻数字的最大乘积。

这里的逻辑是，当我们向左旋转字符串时，字符串的末尾和下一个字符会转到字符串的首位。因此，只需找到相邻字符的最大乘积就足够了。

算法

步骤 1 - 使用相应的值初始化 'len'、'first'、'second' 和 'maximum'。

步骤 2 - 从第二个位置开始遍历字符串。

步骤 3 - 将当前字符放入 'first' 变量，将前一个字符放入 'last' 变量。

步骤 4 - 如果首尾字符的乘积大于 'maximum' 的值，则更新 'maximum' 变量的值。

步骤 5 - 最后返回 'maximum' 变量的值。

示例

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

int getMaxProduct(string num) {
    int len = num.size();
    int first = num[0] - '0';
    int last = num[len - 1] - '0';
    // Get the product of the first and last character of the original string
    int maximum = first * last;
    for (int p = 1; p < len; p++) {
        first = num[p] - '0';
        last = num[p - 1] - '0';
        // Get the product of first and last after rotation by p.
        maximum = max(maximum, first * last);
    }
    return maximum;
}
int main() {
    string num = "9834546";
    cout << "The maximum product of the first and last character after rotation is " << getMaxProduct(num);
    return 0;
}

输出

The maximum product of the first and last character after rotation is 72

时间复杂度 - 对所有相邻字符进行乘积运算，时间复杂度为 O(N)。

空间复杂度 - O(1)，因为我们没有使用额外的空间。

从时间和空间复杂度的角度来看，第二种方法更有效。有时，我们需要观察问题解决方案，并需要根据观察结果编写代码以进一步优化代码。