检查字符是否仅作为单个连续子串出现

---

在这个问题中，我们将检查给定字符串中所有字符是否连续出现。我们将使用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数据结构来解决这个问题，但是程序员可以使用数组数据结构来存储字符的频率。此外，我们可以使用两个嵌套循环来解决这个问题，但是它的时间复杂度可能高于本教程中解释的方法。