字符串中重复字符的最小距离

---

查找字符串中重复字符之间的最小距离是计算机科学中经常遇到的问题。它涉及在给定字符串中找到任意两个相同字符之间的最小距离。例如，在字符串“minimum distance”中，两个'i'之间的最小距离是2，因为它们分别出现在位置1和3。这个问题可以使用不同的编程语言来解决，包括C++。

在本教程中，我们将学习一个C++算法及其实现，以有效地解决这个问题。让我们开始学习一些新的和令人兴奋的东西！

问题陈述

目标是在给定的长度为N的非空字符串S中找到重复字符之间最小的间隔。如果字符串S中没有重复字符，则函数应返回-1。

让我们用例子来理解这个问题陈述。

示例1

输入

S = "tutorialspoints"; N = 15

输出

The shortest distance between repeating characters is 1.

解释：在给定的字符串“tutorialspoints”中，字母't'出现在索引0和2处。这两个't'之间的最小距离是1，这是程序的输出。

示例2

输入

S = "programming"; N = 11

输出

The shortest distance between repeating characters is 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'中减去1以获得重复字符之间的最短距离，并返回该值。

步骤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) {
   // Set the minimum distance to the length of the string, assuming no repeating characters
   int minDistance = str.length();
   // For every character present in the given string
   for (int i = 0; i < len; i++) {
      // For each character that comes after it
      for (int j = i + 1; j < len; j++) {
         // If the characters are identical and the gap between them is smaller than the current minimum distance
         if (str[i] == str[j] && (j - i) < minDistance) {
            // Update the minimum distance
            minDistance = j - i;
            // As this value would be the minimum possible, break from the loop
            break;
         }
      }
   }
   // If the minimum distance is still the length of the string, no repeating characters were found
   if (minDistance == str.length()) {
      return -1;
   } else {
      // Subtract one from the minimum distance to get the shortest distance between repeating characters
      return minDistance - 1;
   }
}
int main() {
   // Example input
   std::string str = "tutorialspoint";
   int len = str.length();
   // Calculate the shortest distance between repeating characters
   int shortestDistance = calculateShortestDistanceBetweenRepeatingChars(str, len);
   if (shortestDistance == -1) {
      std::cout << "No repeating characters found in the string.\n";
   } else {
      std::cout << "The shortest distance between repeating characters is " << shortestDistance << ".\n";
   }
   return 0;
}

输出

The shortest distance between repeating characters is 1.

结论

总而言之，我们讨论了查找给定字符串中相同重复字符之间最小距离的问题。我们提供了对问题陈述的详细解释，以及两个输入输出示例。我们还提供了一个C++程序，该程序使用嵌套循环来比较每一对字符，从而实现有效的解决方案。通过遵循程序中提供的算法，我们可以轻松地找到给定字符串中重复字符之间的最小距离。这个问题通常出现在各种编程面试和编码竞赛中，通过理解本教程中提供的解决方案，我们可以更好地准备应对这些挑战。