Menyemak sama ada rentetan yang diberikan hanya boleh dibahagikan kepada urutan ABC

Satu urutan rentetan ialah sebahagian daripada rentetan di mana aksara boleh diambil dari mana-mana kedudukan (sifar atau lebih elemen) rentetan tanpa mengubah aksara dan membentuk rentetan baru. Dalam masalah ini, kita diberi rentetan panjang N di mana setiap aksara rentetan itu sama ada aksara 'A', 'B' atau 'C'. Tugas kami adalah untuk mencari bahawa rentetan hanya boleh dibahagikan kepada urutan "ABC" atau "Tidak". Mengembalikan "ya" jika rentetan hanya dibahagikan kepada "ABC" yang berikutnya, jika tidak, mengembalikan "tidak".

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

Arahan - Kaedah membelah adalah dengan membelah rentetan kepada 2 urutan "ABC", seperti berikut -

• Salah satu kaedah yang mungkin adalah untuk membentuk urutan "ABC" dengan mengambil aksara dengan indeks 0, 2, dan 3, dan kemudian membentuk jujukan "ABC" dengan mengambil aksara dengan indeks 1, 4, dan 5 ABC".

• Satu lagi cara yang mungkin ialah membentuk "ABC" berikutnya dengan mendapatkan aksara pada indeks 0, 4, 5 dan 1, 2, 3.

Oleh itu, rentetan boleh dibahagikan kepada 2 urutan "ABC".

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

Penjelasan - Untuk 'A' yang terdapat pada indeks nombor 5, tiada 'B' selepasnya. Oleh itu, keseluruhan rentetan tidak boleh dibahagikan kepada "ABC" urutan unik. Oleh itu, jawapannya ialah "tidak".

Kaedah 1: Gunakan Hashmap

Kami mempunyai dua pemerhatian seperti berikut -

• Saiz rentetan hendaklah dibahagikan dengan 3 kerana kita perlu membahagikan rentetan itu kepada "ABC" dan bilangan aksara 'A', 'B' dan 'C' hendaklah sama. Jika tidak, kita tidak boleh memenuhi syarat.

• Apabila kita mengira kekerapan aksara "A", "B" dan "C", kiraan "A" mestilah lebih besar daripada atau sama dengan kiraan "B" dan kiraan "B" mestilah lebih besar daripada atau sama dengan kiraan 'C'. Kerana kiraan A >= kiraan B >= kiraan C

Berdasarkan pemerhatian di atas, kami mempunyai tiga syarat untuk diperiksa.

• Dijangka saiz rentetan % 3 == 0.

• hendaklah kiraan A >= kiraan B >= kiraan C.

• Syarat terakhir hendaklah freq[ ‘A’ ] == freq[ ‘B’ ] == freq[ ‘C’ ] .

Kita boleh menggunakan peta cincang untuk menyelesaikan masalah ini kerana kita perlu menyimpan kekerapan setiap aksara dalam rentetan "str" ​​yang diberikan.

Mari kita bincangkan kaedah berikut langkah demi langkah -

• Pertama kita akan mencipta fungsi yang dipanggil "checkSubsequences" yang akan mengambil rentetan "str" ​​​​sebagai parameter dan mengembalikan rentetan yang diperlukan jika boleh" ya", jika tidak "tidak" dikembalikan sebagai nilai pulangan.

• Dalam fungsi, semua langkah diberikan di bawah -

• Buat pembolehubah "len" untuk menyimpan panjang rentetan.

• Semak syarat pertama dan kembalikan 'tidak' jika panjangnya tidak dibahagikan dengan 3.

• Buat peta cincang untuk menyimpan frekuensi aksara 'A', 'B' dan 'C'. Oleh itu, kerumitan ruang adalah malar.

• Gunakan gelung for untuk melintasi rentetan daripada 0 kepada kurang daripada len.

  • Tingkatkan kiraan aksara semasa dalam rentetan

  • Semak syarat kedua dan kembalikan "Tidak" jika kiraan "A" kurang daripada kiraan "B" atau kiraan "B" kurang daripada kiraan "C".

    li>

• Selepas gelung for, kita perlu menyemak syarat ketiga terakhir dan kembalikan "Tidak" jika kiraan A tidak sama dengan kiraan B atau kiraan B tidak sama dengan kiraan C.

• Akhir sekali, apabila semua syarat dipenuhi, balas "ya".

Contoh

#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;
}

Output

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

Kerumitan Masa dan Ruang

Kerumitan masa kod di atas ialah O(N) kerana kita melintasi rentetan. di mana N ialah saiz rentetan.

Kerumitan ruang kod di atas ialah O(1) kerana kami menyimpan kekerapan nombor, yang saiznya adalah malar 3.

KESIMPULAN

Dalam tutorial ini, kami melaksanakan program untuk menyemak sama ada rentetan yang diberikan hanya boleh dibahagikan kepada urutan ABC. Kami melaksanakan kaedah pencincangan kerana kami perlu menyimpan frekuensi. Dalam kaedah ini, kami terutamanya menyemak tiga syarat, jika semua syarat dipenuhi, ini bermakna kami hanya boleh membahagikan rentetan ke dalam urutan "ABC".

Atas ialah kandungan terperinci Menyemak sama ada rentetan yang diberikan hanya boleh dibahagikan kepada urutan ABC. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!