檢查給定的字串是否只能被拆分為ABC的子序列

字串的子序列是指字串的一部分，其中可以從字串的任何位置（零個或多個元素）取出字符，而無需更改字元的順序並形成新的字串。在這個問題中，我們給出了一個長度為 N 的字串，其中字串的每個字元都屬於「A」、「B」或「C」字元。我們的任務是找到該字串只能拆分為子序列“ABC”或“Not”。如果字串僅拆分為子序列“ABC”，則傳回“yes”，否則傳回“no”。

Input 1: str = “AABCBC” 
Output 1: yes

說明 - 分割的方式是將字串分割成「ABC」的2個子序列，如下 -

• 其中一個可能的方法是，透過取索引為0、2、3的字元形成子序列“ABC”，然後透過取索引為1、4、5的字元形成子序列“ABC” 。

• 另一種可能的方法是，透過在索引0、4、5和1、2、3處取得字元來形成子序列「ABC」。

因此，字串可以拆分為「ABC」的 2 個子序列。

Input 2: str = “AABBBACCC”
Output 2: no

解釋 - 對於在索引號5處出現的'A'，之後沒有'B'。因此，整個字串不能分割為唯一的子序列"ABC"。因此，答案是"no"。

方法1：使用Hashmap

我們有兩個觀察結果如下 -

• 字串的大小應該能被3整除，因為我們需要將字串分割為“ABC”，而且字元'A'、'B'和'C'的數量應該相等。否則，我們無法滿足條件。

• 當我們計算字元「A」、「B」和「C」的頻率時，「A」的計數必須大於等於「B」的計數和「B」的計數' 必須大於等於'C ' 的計數。因為 A 的計數 >= B 的計數 >= C 的 cout

#根據上述觀察，我們有三個條件要檢查。

• 應為字串大小 % 3 == 0。

• 應該是 A 的計數 >= B 的計數 >= C 的計數。

• 最後一個條件應該是 freq[ ‘A’ ] == freq[ ‘B’ ] == freq[ ‘C’ ] 。

我們可以使用雜湊映射來解決這個問題，因為我們需要儲存給定字串「str」中每個字元的頻率。

讓我們逐步討論下面的方法-

• 首先，我們將建立一個名為“checkSubsequences”的函數，該函數將以給定的字串“str”作為參數，並在可能的情況下返回所需的字串“yes” ，否則返回“no”作為返回值。

• 在函數中，下面給出了所有步驟-

• 建立變數「len」來儲存字串的長度。

• 檢查第一個條件，如果長度不能被3整除，則回傳'no'。

• 建立一個雜湊映射來儲存字元'A'、'B'和'C'的頻率。因此，空間複雜度是常數。

• 使用for迴圈從0到小於len遍歷字串。

  • 增加字串目前字元的計數

  • 檢查第二個條件，如果「A」的計數小於「B」的計數或「B」的計數小於「C」的計數，則傳回「否」。

• #在 for 迴圈之後，我們必須檢查最後的第三個條件，如果 A 的計數不等於 B 的計數或 B 的計數不等於 C 的計數，則傳回「否」。

• 最後，當所有條件都滿足時，回傳「yes」。

範例

#include <bits/stdc++.h>
using namespace std;
// function to check subsequences of "ABC"
string checkSubsequences( string str ){
   int len = str.size(); //getting length of the string str
   // check first condition 
   if( len%3 != 0 ) {
      return "no";
   }
   map< char, int >freq; //store the count of character 'A', 'B' and 'C'
   for( int i=0; i<len; i++){
      freq[ str[i] ]++; // increase the count of the character
      //chech second condition 
      if(freq[ 'A' ] < freq[ 'B' ] || freq[ 'B' ] < freq[ 'C' ]){
         return "no";
      }
   }
   //check third condition 
   if(freq[ 'A' ] != freq[ 'B' ] || freq[ 'B' ] != freq[ 'C' ]){
      return "no";
   }
   // it is possible to split string only into subsequences of "ABC"
   return "yes";
}
// main function 
int main(){
   string str = "ABAAABCBC";// given string 
   // calling the function 'checkSubsequences' to check is it possible to split
   // string into subsequences of "ABC"
   string result = checkSubsequences( str );
   if( result == "yes" ){
      cout<< result << ", the string is splited only into the subsequences of ABC";
   }
   else {
      cout<< result << ", the string is not splited only into the subsequences of ABC.";
   }
   return 0;
}

輸出

no, the string is not splited only into the subsequences of ABC.

時間與空間複雜度

上述程式碼的時間複雜度為O(N)，因為我們遍歷了字串。其中N是字串的大小。

上述程式碼的空間複雜度為 O(1)，因為我們儲存的是數字的頻率，其大小恆定為 3。

結論

在本教程中，我們實作了一個程式來檢查給定的字串是否只能拆分為子序列 ABC。我們實作了一種雜湊方法，因為我們必須儲存頻率。在這種方法中，我們主要檢查三個條件，如果所有條件都滿足，則意味著我們只能將字串分割為「ABC」的子序列。

以上是檢查給定的字串是否只能被拆分為ABC的子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！