字母位置和頻率奇偶性相同的字母數量的奇偶性

---

在這個問題中，我們將計算頻率和位置具有相同奇偶性的字元的數量，並將字元數量的奇偶性打印出來。

為了解決這個問題，我們可以找到字串中每個字元的頻率，並計算頻率和位置具有相同奇偶性的字元總數。之後，我們可以根據計數列印奇數或偶數答案。

問題陳述 - 我們給定一個字串 alpha，其中只包含小寫英文字母。我們需要檢查具有其字母位置和頻率相同奇偶性的字元數量是奇數還是偶數。

如果字元滿足以下任何條件，則任何字元具有相同的頻率和字母位置奇偶性。

• 如果字串中字元的頻率為奇數，並且字母位置也為奇數。

• 如果字串中字元的頻率為偶數，並且字母位置也為偶數。

示例

輸入

alpha = "dbbabcdc"

輸出

Even

解釋 

• ‘a’ 的頻率為 1，位置也為 1。因此，兩者具有相同的奇偶性，計數變為 1。

• ‘d’ 的頻率為 2，位置為 4。因此，由於奇偶性位相同，計數變為 2。

計數的值為 2，它是偶數。

輸入

alpha = "ppqqr"

輸出

Odd

解釋 – 只有 ‘p’ 的奇偶性相同。因此，計數為 1，答案為奇數。

輸入

alpha = "pqqqqrrr";

輸出

Even

解釋 – 任何字元的奇偶性都不相同。因此，由於計數值為零，它列印 ‘偶數’。

方法 1

在這種方法中，我們將使用 map 資料結構來儲存每個字串字元的頻率。之後，我們將計算具有字母位置和頻率相同奇偶性的字元的數量。

演算法

步驟 1 - 定義長度為 27 的 count[] 陣列並初始化為 0。此外，將 ‘parity’ 初始化為 0。

步驟 2 - 將字元頻率儲存在 count[] 陣列中。

步驟 3 - 進行 26 次迭代以遍歷每個小寫字母字元。

步驟 4 - 如果 count[p] 大於 0，則檢查字元頻率和位置是否具有相同的奇偶性。如果是，則將 ‘parity’ 值增加 1。

步驟 5 - 最後，如果 parity 可被 2 整除，則返回 ‘偶數’。否則，返回 ‘奇數’。

示例

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

string getParity(string alpha) {
    // To store the count of characters
    int count[27] = {0};
    int parity = 0;
    // Count frequency of each character
    for (int p = 0; p < alpha.size(); p++) {
        count[alpha[p] - 'a' + 1]++;
    }
    for (int p = 1; p <= 26; p++) {
        if (count[p] != 0) {
            // Increment parity for valid odd and even parity
            if (p % 2 == 0 && count[p] % 2 == 0 || p % 2 == 1 && count[p] % 2 == 1)
                parity++;
        }
    }
    // Return value based on final parity count
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "dbbabcdc";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

輸出

The parity of given string's character's is EVEN

時間複雜度 - O(N) 用於計算字元的頻率。

空間複雜度 - O(26) ~ O(1) 用於儲存字母字元的頻率。

方法 2

在這種方法中，我們將對給定的字串進行排序。之後，每當我們獲得不同的相鄰字元時，我們將檢查前一個字元的頻率和位置的奇偶性。

演算法

步驟 1 - 將 ‘parity’ 初始化為 0。

步驟 2 - sort() 方法用於對給定字串進行排序。

步驟 3 - 開始遍歷字串，並將 ‘charCnt’ 初始化為 0 以儲存當前字元的頻率。

步驟 4 - 如果當前字元與下一個字元不同，則檢查 ‘charCnt’ 的奇偶性與字元的位置是否匹配。如果是，則將 ‘parity’ 增加 1。

步驟 5 - 如果當前字元與前一個字元相同，則將 ‘charCnt’ 增加 1。

步驟 6 - 最後，如果 ‘parity’ 值為偶數，則返回 ‘偶數’。否則，返回 ‘奇數’。

示例

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

string getParity(string alpha) {
    int parity = 0;
    // Sort the string
    sort(alpha.begin(), alpha.end());
    // Traverse the string
    for (int p = 0; p < alpha.size(); p++) {
        int charCnt = 0;        
        // When we get different adjacent characters
        if (alpha[p] != alpha[p + 1]) {
            // Validating the odd and even parties
            if (charCnt % 2 == 1 && (alpha[p] - 'a' + 1) % 2 == 1 || charCnt % 2 == 0 && (alpha[p] - 'a' + 1) % 2 == 0)
                parity++;
        } else {
            charCnt++;
        }
    }
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "abbbccdd";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

輸出

The parity of given string's character's is EVEN

時間複雜度 - O(NlogN) 用於對字串進行排序。

空間複雜度 - O(N) 用於對字串進行排序。

第一種方法佔用恆定空間，而第二種方法佔用動態空間對給定字串進行排序。此外，第二種方法在時間上開銷更大，因此建議使用第一種方法以獲得更好的效能。