查詢字元，當增加 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 後出現在字串中的唯一字元的問題。