在给定字符串中从任一端到达最大和最小字符的最小跳跃次数

---

在这个问题中，我们需要找到在给定字符串中到达最大和最小字符所需的最小跳跃次数。我们可以在一次跳跃中移动到下一个或上一个字符。

我们可以通过在给定字符串中找到字典序最大和最小字符的位置来解决这个问题。之后，我们可以找到从字符串的左侧和右侧到达找到的索引所需的最小跳跃次数。

问题陈述 – 我们有一个长度为 N 的字符串 str，其中包含大写的字母字符。我们需要找到从字符串的左侧或右侧到达字典序最小和最大字符所需的最小移动次数。

示例

输入

alpha = "ASDFDJF";

输出

2

解释

• 字典序最小字符是 'A'，其索引为 0。

• 字典序最大字符是 'S'，其索引为 1。

因此，如果我们跳到索引 1，我们也可以到达索引 0。所以，我们需要两次跳跃。一次是从左侧到索引 0，另一次是从索引 0 到索引 1。

输入

alpha = "OPQRSTUV";

输出

2

解释

• 字典序最小字符是 'O'，其索引为 0。

• 字典序最大字符是 'P'，其索引为 7。

我们可以从左侧一步到达索引 0，从右侧一步到达索引 7。因此，我们总共需要 2 步。

输入

alpha = "CDABNFGH"

输出

5

解释 – 如果我们从左侧跳跃 5 次，我们可以到达 'A' 和 'N'，它们分别是字典序最小和最大字符。

方法 1

只有三种方法可以到达这两个字符。第一种方法是从左侧到达这两个字符。第二种方法是从右侧到达这两个字符。第三种方法是从左侧到达一个字符，从右侧到达另一个字符。我们需要取上述所有三种方案中的最小值。

算法

步骤 1 – 定义 largeInd 和 smallInd 变量来存储字典序最小和最大字符的索引。

步骤 2 – 使用循环遍历字符串。在循环中，如果第 p 个索引处的字符大于 ‘largeInd’ 索引处的字符，则将 ‘largeInd’ 更新为 p。

步骤 3 – 如果第 p 个索引处的字符小于 ‘smallInd’ 索引处的字符，则将 ‘smallInd’ 的值更新为 p。

步骤 4 – 声明 ‘minMoves’ 和 ‘maxMoves’ 变量，并将 largeInd 和 smallInd 的最小值和最大值分别存储在这两个变量中。

步骤 5 – 声明 sol1、sol2 和 sol3 变量来存储所有三种方案。

步骤 6 – 在 sol1 中，存储字符串长度 – minMoves 以从右侧到达这两个索引。

步骤 7 – 在 sol2 中，存储 maxMoves + 1 以从左侧到达这两个索引。

步骤 8 – 在 sol3 变量中，存储 minMoves + 1 + str_len – maxMoves 以从左侧到达一个索引，从右侧到达另一个索引。

步骤 9 – 从 sol1、sol2 和 sol3 中取最小值并返回结果。

示例

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

int totalMoves(string alpha, int str_len) {
    // To store positions of the largest and smallest character
    int largeInd = 0, smallInd = 0;
    // Find the index of the largest and smallest character
    for (int p = 0; p < str_len; p++) {
        if (alpha[p] > alpha[largeInd])
            largeInd = p;
        if (alpha[p] < alpha[smallInd])
            smallInd = p;
    }
    // Get the min and max moves
    int minMoves = min(largeInd, smallInd);
    int maxMoves = max(largeInd, smallInd);
    // Finding all possible solutions
    int sol1, sol2, sol3;
    // Jumping to both elements from the right side
    sol1 = str_len - minMoves;
    // Jumping to both elements from the left side
    sol2 = maxMoves + 1;
    // Jumping to min from the left and max from right
    sol3 = minMoves + 1 + str_len - maxMoves;
    // Take a minimum of all possible solutions
    int answer = min(sol1, min(sol2, sol3));
    return answer;
}
int main() {
    string alpha = "ASDFDJF";
    int str_len = alpha.length();
    cout << "The number of minimum moves required to reach the largest and smallest character is - " << totalMoves(alpha, str_len);
    return 0;
}

输出

The number of minimum moves required to reach the largest and smallest character is - 2

时间复杂度 – O(N)，因为我们找到了字典序最大和最小字符的索引。

空间复杂度 – O(1)，因为我们使用常量空间来存储解决方案。

程序员可以解决需要找到到达第二小和最大字符所需最小跳跃次数的问题。到达索引的逻辑相同，但查找第二小和最大字符的索引会发生变化。