# TRISWP - Editorial

Author: mexomerf
Tester: jay_1048576
Editorialist: iceknight1093

TBD

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:
1. S_i = S_{i+1}, like aab. In this case, a left rotation changes the values of indices i+1 and i+2.
2. S_i = S_{i+2}, like aba. In this case, a left rotation changes the values of indices i and i+1,
3. S_{i+1} = S_{i+2}, like baa. In this case, a left rotation changes the values of indices i and i+2.

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.
• The baa case is the only one that changes two spaced-out indices (i and i+2).
• 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.

# 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)

1 Like

So sad, I thought we didn’t need to add string in which we can’t shuffle when s[i] = s[i+1] = s[i+2] since that’s the initial string and that was not counted in example test cases but it is actually also generated after operation -_-

2 Likes

# same bro :cry:

2 Likes

Problem: Triangular Swaps

My Approach: increase ans++ in only two cases not matched. Case:1 → s[i] == s[i+1] && s[i] == s[i+2] and Case:2 → s[i] == s[i+1] && s[i] == s[i+3]. It’ll not get SIGSEV because that edge case has been taken care of.

Issues: It just got wrong on the second answer. What’s wrong in my approach? Can anyone help me to identify?

Code:

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

int n;
bool skip(string &str, int i)
{
if (str[i] == str[i + 1] && str[i] == str[i + 2])
return 1;

if (i < n - 3 && str[i] == str[i + 1] && str[i] == str[i + 3])
return 1;

return 0;
}

void solve()
{
cin >> n;

string str;
cin >> str;

vector<string> strings;
strings.push_back(str);

int ans = 0;
for (int i = 0; i < n - 2; i++)
{
if (!skip(str, i))
ans++;
}

cout << ans;
}

int main()
{
int t;
cin >> t;

while (t--)
{
solve();
cout << '\n';
}

return 0;
}

1 Like

I got my answer. Actually, aaa is also a distinct string. I ignore this case. so for every s1 == s2 == s3, need to count just 1. That’s it.

Updated Code:

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

int n;
bool skip(string &str, int i)
{
if (str[i] == str[i + 1] && str[i] == str[i + 2])
return 1;

if (i < n - 3 && str[i] == str[i + 1] && str[i] == str[i + 3])
return 1;

return 0;
}

void solve()
{
cin >> n;

string str;
cin >> str;

vector<string> strings;
strings.push_back(str);

int ans = 0, addOne = 0;
for (int i = 0; i < n - 2; i++)
{
if (str[i] == str[i + 1] && str[i] == str[i + 2])
if (!skip(str, i))
ans++;
}

}

int main()
{
int t;
cin >> t;

while (t--)
{
solve();
cout << '\n';
}

return 0;
}


baoooo niice question just missed that edge case of all equalssss