字串中重複字元的最小距離

---

查詢字串中重複字元之間的最小距離是計算機科學中經常遇到的問題。它涉及在給定字串中找到任意兩個相同字元之間的最小距離。例如，在字串“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++程式，該程式使用巢狀迴圈來比較每一對字元，從而實現有效的解決方案。透過遵循程式中提供的演算法，我們可以輕鬆地找到給定字串中重複字元之間的最小距離。這個問題通常出現在各種程式設計面試和編碼競賽中，透過理解本教程中提供的解決方案，我們可以更好地準備應對這些挑戰。