# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* mexomerf

*jay_1048576*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You have a string S.

In one move, you can choose an index i (1 \leq i \leq |S|-2), and left-rotate the substring S_iS_{i+1}S_{i+2}, turning it into S_{i+1}S_{i+2}S_i.

How many distinct strings can be obtained by performing this operation exactly once?

# EXPLANATION:

Let’s look at three consecutive characters starting from index i, and how rotating them changes the string.

There are three cases.

- S_i = S_{i+1} = S_{i+2}, i.e all three are the same.

In this case, rotating them effectively changes nothing. - S_i, S_{i+1}, S_{i+2} are all distinct (for example
`abc`

).

In this case, a left rotation will change the values at all three indices. - Some two of the three characters are equal, and the third is not equal to them.

In this case, there are again three possibilities:- S_i = S_{i+1}, like
`aab`

. In this case, a left rotation changes the values of indices i+1 and i+2. - S_i = S_{i+2}, like
`aba`

. In this case, a left rotation changes the values of indices i and i+1, - S_{i+1} = S_{i+2}, like
`baa`

. In this case, a left rotation changes the values of indices i and i+2.

- S_i = S_{i+1}, like

Analyzing all the cases, it can be seen that:

- The “all three equal” case doesn’t change S at all, and is the only type that can attain this.

However, applying it at different indices give the same final string; so this case adds either zero or one to the answer, depending on whether such a triple exists at all. - The “all distinct” case is the only one that changes three indices; and each such one will result in a different string since a different set of indices will be changed.

So, for*each*such type, add 1 to the answer. - The
`baa`

case is the only one that changes two*spaced-out*indices (i and i+2).

So, for each such type, add 1 to the answer. - The
`aba`

and`aab`

cases can overlap - for example as seen in`aaba`

, where rotating either the first or the second length-3 substring will result in`abaa`

.

If there is no overlap, each occurrence of this type will result in a distinct final string.

To account for this,- Add 1 to the answer for each occurrence of type
`aba`

. - Add 1 to the answer for each occurrence of type
`aab`

that’s*not*immediately followed by`aba`

.

This ensures that for each ‘overlap’, we add only 1 to the answer and not 2.

- Add 1 to the answer for each occurrence of type

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Tester's code (C++)

```
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
string shift(string s,int i)
{
char a=s[i],b=s[i+1],c=s[i+2];
s[i]=b,s[i+1]=c,s[i+2]=a;
return s;
}
void solve(int tc)
{
int n;
cin >> n;
string s;
cin >> s;
int ans=n-2,cnt=0;
for(int i=0;i<n-2;i++)
{
if(i<n-3 && s[i]==s[i+1] && s[i]==s[i+3])
ans--;
else if(s[i]==s[i+1] && s[i]==s[i+2])
{
ans--;
cnt++;
}
}
cout << ans+min(1ll,cnt) << '\n';
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
s = input()
ans = 0
same = 0
for i in range(n-2):
st = {s[i], s[i+1], s[i+2]}
if len(st) == 1: same = 1
elif len(st) == 3: ans += 1
else:
if i == 0 or s[i] != s[i+2] or s[i] != s[i-1]: ans += 1
print(ans+same)
```