字符串中重复项之间的最小距离
查找字符串中重复项之间的最小距离是计算机科学中经常遇到的问题。它涉及找出给定字符串中任意两个相同字符之间的最小距离。例如，在字符串"minimum distance"中，两个"i"之间的最小距离为2，因为它们分别出现在位置1和位置3。这个问题可以使用不同的编程语言来解决，包括C++。
在本教程中，我们将学习一个C++算法及其实现，以有效地解决这个问题。那么，让我们开始学习一些新鲜有趣的东西吧!
问题描述
目标是在给定的长度为 N 的非空字符串 S 中，找出两个重复的相同字符之间的最小间隔。如果字符串 S 中没有重复字符，函数应该返回 -1。
让我们通过示例来理解这个问题的描述。
示例 1
输入
S = "tutorialspoints"; N = 15
输出
重复字符之间的最短距离为 1。
解释:在给定的字符串"tutorialspoints"中，字母"t"出现在索引 0 和 2 处。这两个"t"之间的最小距离为 1，即程序的输出。
示例 2
输入
S = "programming"; N = 11
输出
重复字符之间的最短距离为 1。
解释:在给定的字符串"programming"中，重复字符之间的最小距离为"0"，因为字母"m"在索引 6 和 7 处连续出现两次。
算法
给定字符串中相同重复字符之间最小距离的算法:
步骤 1:定义一个函数"calculateShortestDistanceBetweenRepeatingChars"，以"std::string"及其长度"len"作为输入参数。
步骤 2:假设未找到重复字符，将最小距离"minDistance"设置为字符串的长度。
步骤 3:对于每个字符"i"在字符串中，迭代所有后续字符"j"。
步骤 4:如果"i"和"j"是同一个字符，并且它们之间的距离小于当前的 minDistance，则将 minDistance 更新为新的距离。
步骤 5:如果"minDistance"仍然是字符串的长度，则表示未找到重复字符，因此返回 -1。
步骤 6:否则，将"minDistance"减一以获取重复字符之间的最短距离，并返回该值。
步骤 7:在"main()"中，定义一个字符串"str"及其长度"len"，然后调用"calculateShortestDistanceBetweenRepeatingChars"并将结果存储在"shortestDistance"中。
步骤 8:输出结果:如果"shortestDistance"为 -1，则输出"未找到重复字符"字符串。"，否则输出"重复字符之间的最短距离为'shortestDistance'。"。
现在，在理解了算法之后，是时候使用 C++ 实现上述算法了。我们将借助一个例子来实现。那就让我们开始吧!
示例
使用 C++ 实现上述算法
下面的 C++ 程序计算给定字符串中两个重复字符之间的最短距离并输出结果。它通过遍历字符串中的每个字符并将其与所有后续字符进行比较来实现，从而跟踪迄今为止找到的重复字符之间的最小距离。如果没有找到重复字符，程序返回 -1，否则输出重复字符之间的最短距离。
#include <iostream>
#include <string>
#include <algorithm>
int calculateShortestDistanceBetweenRepeatingChars(const std::string& str, int len) {
// 假设没有重复字符，将最小距离设置为字符串的长度
int minDistance = str.length();
// 对于给定字符串中存在的每个字符
for (int i = 0; i < len; i++) {
// 对于其后的每个字符
for (int j = i + 1; j < len; j++) {
// 如果字符相同，且它们之间的间隔小于当前的最小距离
if (str[i] == str[j] && (j - i) < minDistance) {
// 更新最小距离
minDistance = j - i;
// 由于此值是可能的最小值，因此退出循环
break;
}
}
}
// 如果最小距离仍然是字符串的长度，则表示未找到重复字符
if (minDistance == str.length()) {
return -1;
} else {
// 从最小距离中减一，得到重复字符之间的最短距离
return minDistance - 1;
}
}
int main() {
// 示例输入
std::string str = "tutorialspoint";
int len = str.length();
// 计算重复字符之间的最短距离
int shortestDistance = calculateShortestDistanceBetweenRepeatingChars(str, len);
if (shortestDistance == -1) {
std::cout << "No repeating characters found in the string.\n";
} else {
std::cout << "重复字符之间的最短距离为 " << shortestDistance << ".\n";
}
return 0;
}
输出
重复字符之间的最短距离为 1。
结论
总而言之，我们讨论了在给定字符串中找出相同重复字符之间最小距离的问题。我们提供了问题陈述的详细解释，以及两个输入输出示例。我们还提供了一个 C++ 程序，该程序使用嵌套循环比较每对字符来实现高效的解决方案。通过遵循程序中提出的算法，我们可以轻松地找到给定字符串中重复字符之间的最小距离。这个问题在各种编程面试和编程比赛中经常遇到，通过理解本教程中提供的解决方案，我们可以更好地准备应对此类挑战。
