透過將子音替換為最接近的母音，反之亦然，來計算唯一字串的數量

---

在這個問題中，我們將計算透過替換每個母音為最接近的子音，每個子音為最接近的母音，可以生成的唯一字串的數量。

我們可以找到每個字元替換當前字元為其他字元的選擇數量。之後，我們可以將每個字元的選擇數量相乘得到答案。

問題陳述

我們給定了一個字母字串。我們需要計算透過對字串的每個字元執行以下操作，可以從給定字串生成的不同字串的總數

• 將母音更改為任何最接近的子音。

• 將子音更改為任何最接近的母音。

• 不考慮迴圈距離。

示例

Input –  alpha = "abcd"
Output – 2

解釋

• 我們可以用“b”替換“a”。

• 我們可以用“a”替換“b”。

• 我們可以用“a”或“e”替換“c”。

• 我們可以用“e”替換“d”。

因此，替換字串每個字元的選擇是 1、1、2、1。當我們將所有選擇相乘時，我們得到 2 作為答案。

Input –  alpha = "cglr"
Output – 16

解釋

我們有兩個選擇來用兩個母音替換字串的每個字元。

Input –   alpha = "pppppp"
Output – 1

解釋

由於所有字元都相同，並且我們可以用“o”替換“p”，因此答案是 1。

方法 1

在這種方法中，我們將母音的位置儲存在對映中以查詢最接近的子音。對於除了“a”之外的每個母音，都有兩個選擇用子音替換字元。

此外，“c”、“g”、“l”和“r”子音有兩個選擇用最接近的母音替換，而其他子音只有一個選擇。對於子音，我們可以找到替換每個字元的選擇，並將每個選擇相乘以獲得答案。基本上，這個問題非常類似於根據給定條件找到總排列。

演算法

• 步驟 1 - 初始化“cnt”為 1 以儲存答案。

• 步驟 2 - 將所有母音儲存在“vowels”對映中，並帶有其 0 為基的索引。

• 步驟 3 - 開始遍歷字串，並在“vowels”對映中查詢字元。

• 步驟 4 - 如果字元在母音對映中不存在，則檢查字元是否為“c”、“g”、“l”或“r”。如果是，則將“cnt”值乘以 2。

• 步驟 5 - 如果字元存在於母音對映中，並且字元不是“a”，則將“cnt”值乘以 1。

• 步驟 6 - 返回“cnt”值。

示例

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

int calculateUniqueStrings(string alpha) {
   int len = alpha.size();
   int cnt = 1;
   
   // Map for vowels
   map<char, int> vowels;
   vowels['a'] = 0;
   vowels['e'] = 4;
   vowels['i'] = 8;
   vowels['o'] = 14;
   vowels['u'] = 20;
   for (int p = 0; p < len; p++) {
   
      // For consonants
      if (vowels.find(alpha[p]) == vowels.end()) {
         int ch = alpha[p] - 'a';
         // For c, g, l, and r consonants
         if (ch == 2 || ch == 6 || ch == 11 || ch == 17)
         cnt *= 2;
      }
      
      // For vowel
      else {
      
         // Each vowel has two choices except 'a'
         if (alpha[p] != 'a')
         cnt *= 2;
      }
   }
   return cnt;
}
int main() {
string alpha = "abgd";
cout << "The total unique strings we can get by replacing the characters is " << calculateUniqueStrings(alpha) << endl;
return 0;
}

輸出

The total unique strings we can get by replacing the characters is 2

• 時間複雜度 - O(N)，用於替換字串的每個字元。

• 空間複雜度 - O(1)，因為我們沒有使用任何額外的空間。

我們學習瞭如何透過用最近的母音或子音替換字串的每個字元來查詢不同字串的數量。程式設計師可以解決僅替換單個字元的問題，即計算可以形成的不同字串的數量。