DIFFPENS - Editorial

PROBLEM LINK:

Practice

Contest

Author and Editorialist: Prathmesh Patil

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

A short and concise description of the problem statement.

QUICK EXPLANATION:

You are given a set of n pens, each of them can be red, blue, green, orange, and violet in color. You are given a string that contains ‘R’, ‘B’, ‘G’, ‘O’, and ‘V’ characters that represent the color of pens. You have to count a minimum number of pens that should be taken out from the set so that any two neighboring pens have different colors.

EXPLANATION:

The characters represent the color of pens.

We can get our desired sequence when neighboring pens have a different color. That is, No two neighboring pens should have the same color.

Thus, we will have to remove neighboring pens that have the same color to obtain our desired sequence of pens.
For eg. let’s consider the sequence ‘RGRRBBVO’, in this sequence if we remove R at the 4th position, B at the 6th position. Then the resultant sequence will be ‘RGRBVO’ which is our desired sequence.

So, we will count the number of neighboring pens that share a common color.

For this, we will traverse the string and see if the current character is same as next character i.e
‘i’ th character is the same as ‘i+1’ th character, if both are the same then we will increase the count and after the traversal of string, we will print the count.

Let’s consider the same example ‘RGRRBBVO’, here R at the 3rd position is neighboring to R at 4th position. Similarly, B at the 5th position is neighboring to B at the 6th position. Thus we can see that two ‘i’ th characters are the same as ‘i+1’ th characters.

SOLUTIONS:

Solution

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

int main()
{
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;
string s;
cin >> s;
int cnt=0;
for(int i=0;i<n-1;i++)
{
if(s[i]==s[i+1])
cnt++;
}
cout << cnt << endl;
}
}

Please feel free to share your solution! :smile:

1 Like