Vérifie si la chaîne donnée ne peut être divisée qu'en sous-séquences de ABC

Une sous-séquence d'une chaîne est une partie d'une chaîne où des caractères peuvent être extraits de n'importe quelle position (zéro ou plusieurs éléments) de la chaîne sans changer l'ordre des caractères et former une nouvelle chaîne. Dans ce problème, nous recevons une chaîne de longueur N où chaque caractère de la chaîne est soit un caractère « A », « B » ou « C ». Notre tâche est de constater que la chaîne ne peut être divisée qu'en sous-séquences « ABC » ou « Not ». Renvoie "oui" si la chaîne est uniquement divisée en sous-séquence "ABC", sinon renvoie "non".

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

Instructions - La méthode de fractionnement consiste à diviser la chaîne en 2 sous-séquences de "ABC", comme suit -

• Une des méthodes possibles est de former la sous-séquence "ABC" en prenant les caractères d'index 0, 2 et 3, puis de former la sous-séquence "ABC" en prenant les caractères d'index 1, 4 et 5.

• Une autre manière possible est de former la sous-séquence "ABC" en récupérant les caractères aux index 0, 4, 5 et 1, 2, 3.

Ainsi, la chaîne peut être divisée en 2 sous-séquences de « ABC ».

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

Explication - Pour « A » apparaissant au numéro d'index 5, il n'y a pas de « B » après. Par conséquent, la chaîne entière ne peut pas être divisée en une sous-séquence unique « ABC ». La réponse est donc « non ».

Méthode 1 : Utiliser Hashmap

Nous avons deux observations comme suit -

• La taille de la chaîne doit être divisible par 3 car nous devons diviser la chaîne en « ABC » et le nombre de caractères « A », « B » et « C » doit être égal. Sinon, nous ne pouvons pas remplir les conditions.

• Lorsque nous comptons les fréquences des caractères « A », « B » et « C », le nombre de « A » doit être supérieur ou égal au nombre de « B » et le nombre de « B » doit être supérieur ou égal au nombre de « C ». Parce que le nombre de A >= le nombre de B >= le nombre de C

Sur la base des observations ci-dessus, nous avons trois conditions à vérifier.

• doit être une taille de chaîne % 3 == 0.

• devrait être le nombre de A >= le nombre de B >= le nombre de C.

• La dernière condition doit être freq[ 'A' ] == freq[ 'B' ] == freq[ 'C' ] .

Nous pouvons utiliser une carte de hachage pour résoudre ce problème car nous devons stocker la fréquence de chaque caractère dans la chaîne donnée "str".

Discutons de la méthode ci-dessous étape par étape-

• Tout d'abord, nous allons créer une fonction appelée "checkSubsequences" qui prendra la chaîne donnée "str" ​​​​comme paramètre et renverra la chaîne requise "yes" si possible, sinon elle renverra " no " comme valeur de retour.

• Dans la fonction, toutes les étapes sont données ci-dessous -

• Créez la variable "len" pour stocker la longueur de la chaîne.

• Vérifiez la première condition et renvoyez 'non' si la longueur n'est pas divisible par 3.

• Créez une carte de hachage pour stocker les fréquences des caractères « A », « B » et « C ». La complexité spatiale est donc constante.

• Utilisez une boucle for pour parcourir la chaîne de 0 à moins que len.

  • Augmente le nombre actuel de caractères de la chaîne

  • Vérifiez la deuxième condition et renvoyez « Non » si le nombre de « A » est inférieur au nombre de « B » ou si le nombre de « B » est inférieur au nombre de « C ».

• Après la boucle for, nous devons vérifier la dernière troisième condition et renvoyer "Non" si le nombre de A n'est pas égal au nombre de B ou si le nombre de B n'est pas égal au nombre de C.

• Enfin, lorsque toutes les conditions sont remplies, répondez « oui ».

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N) car nous parcourons la chaîne. où N est la taille de la chaîne.

La complexité spatiale du code ci-dessus est O(1) car nous stockons la fréquence du nombre, dont la taille est constante 3.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour vérifier si une chaîne donnée peut être divisée uniquement en sous-séquences ABC. Nous avons mis en place une méthode de hachage car nous devions stocker les fréquences. Dans cette méthode, nous vérifions principalement trois conditions, si toutes les conditions sont remplies, cela signifie que nous ne pouvons diviser la chaîne qu'en sous-séquences de "ABC".

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!