查找字符，当增加 K 后出现在字符串中

---

在这个问题中，我们将找到字符串的所有唯一字符及其在字符串中出现的第一个索引，前提是将给定字符串的所有字符增加 K。

为了解决问题，我们可以获取给定字符串的每个唯一字符。接下来，我们可以分别更新每个字符，并检查更新后的字符是否出现在字符串中，并且没有更新为另一个字符以获得答案。

问题陈述 - 我们给定一个字符串 alpha 和一个正整数 K。我们需要将给定字符串的每个字符的 ASCII 值增加 K，并检查更新后的字符是否出现在字符串中。我们需要打印有效的唯一字符及其第一个索引。

示例

输入

alpha = "absstdrc"; K = 2;

输出

0 a
1 b
6 r

解释 - 让我们分别更新每个字符以获得答案。

• ‘a’ + 2 -> ‘c’ = ‘c’ 出现在字符串中，并且尚未更新。

• ‘b’ + 2 -> ‘d’ = ‘d’ 出现在字符串中，并且尚未更新。

• ‘b’ + 2 -> ‘d’ = ‘d’ 出现在字符串中，并且尚未更新。

• ‘t’ + 2 -> ‘v’ = ‘v’ 不在字符串中。

• ‘d’ + 2 -> ‘f’ = ‘f’ 不在字符串中。

• ‘r’ + 2 -> ‘t’ = ‘t’ 没有更新为 ‘v’。因此，我们可以将 ‘r’ 视为输出。

• ‘c’ + 2 = ‘e’ = ‘e’ 不在给定字符串中。

输入

alpha = "abcdefg"; K = 0;

输出

0 a
1 b
2 c
3 d
4 e
5 f
6 g

解释 - 所有字符在更新后都将出现，因为我们将其更新了 0。

输入

alpha = "pqrpqrt"; K = 2;

输出

0 p 

解释 - 我们只能取 ‘p’，因为 ‘p’ + 2 = ‘r’。之后，我们不能更新 ‘r’。此外，‘q’ + 2 是 ‘s’。因此，我们不能在输出中考虑 ‘q’。

方法 1

在这种方法中，我们将给定字符串的唯一字符存储在集合中。之后，我们将遍历字符串的每个字符，将字符增加 K，并检查更新后的字符是否出现在字符串中，并且之前没有访问过原始字符和更新后的字符。如果所有条件都为真，我们可以将原始字符及其索引包含在输出中。

算法

步骤 1 - 创建一个字符的 ‘pairSet’ 集合。

步骤 2 - 遍历字符串，并将每个字符串字符插入集合中。

步骤 3 - 创建一个列表以存储索引和字符的配对。此外，创建长度为 26 的 visited[] 来跟踪特定字符是否之前被访问过。

步骤 4 - 开始遍历字符串，并在将 K 加到原始字符的 ASCII 值后，在 ‘res’ 变量中获取更新后的字符值。

步骤 5 - 如果 ‘res’ 值介于 ‘a’ 和 ‘z’ 之间，请执行以下步骤。否则，转到下一个迭代。

步骤 6 - 如果 ‘res’ 字符出现在映射中，‘res’ 字符之前没有被访问过，并且 alpha[p] 也未被访问过，则更新 visited[] 数组以表示原始字符和更新后的字符，并将包含索引 p 和 alpha[p] 的对插入列表中。

步骤 7 - 最后返回 ‘list’。

示例

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

vector<pair<int, char>> getCharacters(int k, string alpha) {
    set<char> pairSet;
    // Add unique characters in the set
    for (int p = 0; p < alpha.size(); p++) {
        pairSet.insert(alpha[p]);
    }
    // To store final answer
    vector<pair<int, char>> list;
    // To store visited characters
    vector<int> visited(26, 0);
    // Traverse the string
    for (int p = 0; p < alpha.size(); p++) {
        // Get updated character
        char res = char((int(alpha[p]) + k));
        // If the updated character is an alphabetical character
        if (res >= 'a' && res <= 'z') {
            // When the character is present in the set and not visited
            if (pairSet.find(res) != pairSet.end() && !visited[res - 'a'] && !visited[alpha[p] - 'a']) {
                visited[res - 'a'] = visited[alpha[p] - 'a'] = 1;
                // Push index and character in the list
                list.push_back(make_pair(p, alpha[p]));
            }
        }
    }
    return list;
}
int main() {
    string alpha = "absstdrc";
    int K = 2;
    vector<pair<int, char>> res = getCharacters(K, alpha);
    cout << "The characters which are present in the string after incrementing its ASCII values by K are - " << endl;
    for (auto pair : res)
        cout << pair.first << " " << pair.second << endl;
    return 0;
}

输出

The characters which are present in the string after incrementing its ASCII values by K are − 
0 a
1 b
6 r

时间复杂度 - O(N) 用于将字符插入集合中。

空间复杂度 - O(1)，因为我们始终需要使用大小为 26 的集合。

我们学习了如何在将其增加 K 后，找到给定字符串中存在的所有字符串字符。程序员可以尝试解决需要查找在减少 K 后出现在字符串中的唯一字符的问题。