problem link : Problem - A - Codeforces

why this approach is not working ?

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 1;

const int MOD = 1e9 + 7;

const int INF = 1e9;

void solve() {

```
int n;
cin>>n;
char arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int a[n];
bool flag = true;
for(int i=0;i<n;i++)
{
a[i] = arr[i]-'0';
}
for(int i=0;i<n;i++)
{
if(a[i] <= a[i+1])
{
flag = true;
}
}
if(flag)
{
cout<<"YES"<<"\n";
}
else
{
cout<<"NO"<<"\n";
}
```

}

int main() {

```
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc ;
cin>>tc;
while(tc--)
{
solve();
}
return 0;
```

}

Can you explain your logic because it would be easy to debug the code then!!

It feels like somewhere you are logically wrong.

Please note that:

The sequence could be ADDCC and still the teacher won’t have any suspicion it is not necessary that the letters are arranged alphabetically(lexicographically)

Maybe thats where you went wrong!!

AADA → teacher would have suspicion(OP : “NO”)

BBAA → teacher wont have suspicion (OP : “YES”)

Yes some logic would be good.

I personally would make an array of all alphabets and just update it like so:

alpha[str[a] - “A”]++

I would update it as long as the last letter that we updated was the same character as the current one, i.e

if(str[a-1] == str[a])

Now if they are not the same I would check their recorded frequency in the alpha array and if it is greater than zero, it would mean that it has occured somewhere before. Simple O(n) solution.

Yaa, Yesterday I approached it through the same approach.We can even solve the problem using maps .For instance, If we have a sequence like AABBCC

we can consider AA to be as A, BB as B ,CC as C so that when we encounter these letters next time we can simply increment the count…

if the count is greater than 1 then teacher would have suspicion else no suspicion.

Time complexity would be greater than the above approach but this approach is also accepatable.

Hey, your solution is always giving you “YES”, cause you have never turn your flag to false. The logic is wrong too.

Anyway you can try this: take a variable let’s say it c and assign it to the first character of input string.

Run a loop from i=1, i<n, check if s[i] != c, if so, run a loop from j=i+1, j<n. Inside second loop check if s[j] == c, if so, turn flag to false and break, exit second if, exit second loop and reassign c = s[i], exit first if, exit first loop.

Now you can say “YES” if flag is true else “NO”.

Hey @fake_revenge , you logic seems to be somewhere wrong for this problem.

Find out the best explanation and solution of the problem here.

**Link to solution and explanation**

1 Like

Hey, I got your logic but I think you are missing some edge cases…

A better approach will be just taking input of characters in vector and while taking input use FIND(STL) to check whether the char is already present or not…If it is present then chech whether it is the previous char in vector or not…

If not ouput NO and return.

Otherwise at end just cout YES.

BY this approach time complexity will also get reduced…

Hope you like it…

Hey your whole logic is wrong in this question u have to just basically see the different characters occurring in order and if any charater occurs more than you have to output “NO” else “YES”.

int n;

cin>>n;

string s;

cin>>s;

int a[26]={0};

char k=s[0];

a[s[0]-‘A’]++;

for(int i=0;i<s.length();i++){

if(s[i]==k){

continue;

}

else{

k=s[i];

a[k-‘A’]++;

}

}

bool m=true;

for(int i=0;i<26;i++){

if(a[i]>1){

cout<<“NO”<<endl;

m=false;

break;

}

}

if(m){

cout<<“YES”<<endl;

}

A BETTER APPROACH IS TO TRANSVERSE ARRAY FORM STARTING

TAKE A ARRAY TO STORE THE OCCURENCES OF EACH LETTER

WHILE TRANSVERSING THROUGH THE STRING

**CHECK FOR EACH CHARACTER IF ITS OCCURENCE IS ZERO OR NON-ZERO**

→ **IF ITS ZERO** THEN INCREMENT ITS OCCURENCE

AFTER INCREMENTING **START A WHILE LOOP** WHICH WILL I**NCREMENT THE ****

** INDEX WHICH WE ARE TRANSVERSING TILL THE CONSECUTIVE CHARACTERS

ARE SAME.

→ **IF ITS NON-ZERO** :- HERE IS WHERE YOU HAVE TO BREAK TRANSVERSING THE STRING

i.e. WHERE **TEACHER IS SUPSCIOUS**, **you can use a bool here to verify this**

condition

NOW AFTER TRANSERVSING **CHECK YOUR BOOL ACCORDING TO IT OUTPUT YES OR NO**

Let a be the input array. Instead of storing characters 'a', 'b',\cdots we can instead store numbers 1, 2, \cdots.

The cleanest \mathcal{O}(n) approach would be to store an array lst_i for 1 \leqslant i \leqslant 26 which stores the last indice of a at the current moment. Initialize some boolean value truth = 1 and run a loop through the array a. In the i th operation we check if i-lst_{a_i} is equal to 1. If not we change truth to 0. After this we update lst_{a_i} = i.

Hope this approach helps…