PROBLEM LINK:
Author: Pranjul Pal
Tester: Khushi Agarwal
Editorialist: Pranjul Pal
DIFFICULTY:
SIMPLE
PREREQUISITES:
Optimization, Brute Force
PROBLEM:
Find the number of valid triplets in the string built up of characters R, G, and O, of length N.
Valid triplets (i,j,k) (1 \le i \lt j \lt k \le N):
- S_i \ne S_j, S_i \ne S_k, S_j \ne S_k.
- j - i \ne k - j
QUICK EXPLANATION:
Remove invalid distinct-characters triplets from total numbers of invalid distinct-characters triplets.
EXPLANATION:
Let total number of R in string = r
Let total number of G in string = g
Let total number of O in string = o
There are two validations given in the problem statement.
Total number of triplets following first validation = r \times g \times o.
But this number also contains equidistant distinct characters.
To remove these types of triplets, a nested loop will work.
Consider a distance x and remove the triplets (i,j,k) such that (1 \le i \lt j \lt k \le N) and (j - i = k - j) from your answer which have distinct characters.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ln "\n"
#define pb push_back
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define vll vector<ll>
#define vpll vector<pll>
#define vvll vector<vector<ll>>
#define sll stack<ll>
#define qll queue<ll>
#define mp make_pair
#define f first
#define s second
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define Test ll t;cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define init(x,n,v) for(ll i=0;i<=n;i++) x[i]=v;
#define all(x) x.begin(),x.end()
#define pi 3.14159265358979323846
ll MOD = 1e9+7 , MAX = 1e18;
int main()
{
fast_io;
ll n,i,ans=0,r=0,g=0,o=0,j;
string s;
cin>>n>>s;
for(auto i: s)
{
if(i=='R') r++;
if(i=='G') g++;
if(i=='O') o++;
}
ans=r*g*o;
for(i=0;i<n-2;i++)
{
for(j=1;i+2*j<n;j++)
{
if(s[i]!=s[i+j] && s[i]!=s[i+2*j] && s[i+j]!=s[i+2*j]) ans--;
}
}
cout<<ans;
return 0;
}