檢查字元是否僅作為單個連續子串出現

---

在這個問題中，我們將檢查給定字串中所有字元是否連續出現。我們將使用map資料結構來解決這個問題。

map將跟蹤特定字元的最後一個索引，並根據當前字元的最後一個索引，我們將確定字串是否包含連續的字元。

問題陳述 – 我們給定一個長度為N的字串alpha，其中包含小寫和大寫字母字元。我們需要檢查給定的字串是否連續。只有當字串包含所有字元作為連續子串時，該字串才是連續的。因此，相同字元之間不應該有其他字元。

示例

輸入

alpha = "PPQQpp"

輸出

 Yes

解釋 – 字串連續包含所有字元。所以，它列印'Yes'。

輸入

alpha = "PQPQQpp"

輸出

‘No’

解釋 – 'Q'位於兩個'P'之間。所以，字串不連續。

輸入

alpha = "PpPQQpp"

輸出

‘No’

解釋 – 小寫'p'位於大寫'P'之間。所以，字串不連續。

方法一

在這種方法中，我們將使用map來儲存字串字元的位置，表示字元在字串中的最後位置。如果map中儲存的最後位置不相鄰，我們可以說字串不連續。

演算法

步驟1 – 定義'position' map來儲存字元作為鍵，整數作為值。

步驟2 – 開始迭代給定的字串。

步驟3 – 如果字元作為map鍵存在，則執行以下步驟。否則，將字元新增到map中，值為索引+1。

步驟4 – 從map中獲取當前字元的最後位置，如果(索引 - 最後位置 + 1)小於或等於1，則使用當前索引更新字元的位置。

步驟5 – 返回false，因為字串不連續。

步驟6 – 最後，如果字串有效，則返回true。

示例

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

bool checkContinuous(string alpha) {
	unordered_map<char, int> position;
	for (int p = 0; p < alpha.length(); p++) {
		// Check whether the character present in the hashmap or not
		if (position[alpha[p]]) {
			// Check whether the last occurrence is adjacent or not
			if (p - position[alpha[p]] + 1 <= 1) {
				position[alpha[p]] = p + 1;
			} else {
				return false;
			}
		}
		else {
			position[alpha[p]] = p + 1; // Add the position of the character
		}
	}
	return true;
}
int main() {
	string alpha = "PPQQpp";
	if (checkContinuous(alpha)) {
		cout << "Yes, String is continuous!";
	} else {
		cout << "No, String is not continuous!";
	}
	return 0;
}

輸出

Yes, String is continuous!

時間複雜度 – 遍歷字串為O(N)。

空間複雜度 – 儲存最後一個字元位置為O(N)。

我們使用map資料結構來解決這個問題，但是程式設計師可以使用陣列資料結構來儲存字元的頻率。此外，我們可以使用兩個巢狀迴圈來解決這個問題，但是它的時間複雜度可能高於本教程中解釋的方法。