1168B - Good Triple - CodeForces Solution

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 998244353 

ll min(ll a , ll b) {
    return a> b ? b : a ;
}
ll max(ll a, ll b) {
    return a> b ? a : b ;
}

ll find_gcd(ll a, ll b) {
    if(b>a) swap(a,b) ;

    if(a%b==0) return b ;
    return find_gcd(b,a%b) ;
}

ll find_lcm(ll prev_lcm, ll current_val) {
    return (prev_lcm/find_gcd(prev_lcm,current_val))*current_val ;
}


int mul(ll a ,ll b) {
    if((ll)a*b > mod) {
        return (a*b)%mod ;
    }
    return a*b ;

}

int binpow(int x, int y) {
    int z = 1;
    while(y)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x) {
    return binpow(x, mod - 2);    
}

int divide(int x, int y) {
    return mul(x, inv(y));
}

int convert_binary_to_base10(string number){
    int converted_number = 0 ;
    int pow_two = 1;
    for(int i = number.size() ; i>=0 ;i--){
        if(number[i]=='1') {
            converted_number+=pow_two ;
        }
        pow_two*=2 ;
    }
    return converted_number/2 ;
}

ll convert_stringint_to_int(string number){
    ll int_number = 0;
    ll pow_ten = 1;
    for(int i= number.size()-1 ; i>=0 ; i--){
        int_number+=(pow_ten*(number[i]-'0')) ;
        pow_ten = pow_ten*10 ;
    }
    return int_number ;
}


int fill_weighted_value_from_string(string strr, vector<int>&w) {
    int cal_val = 0;
    for(int i = w.size()-1 ; i>=0 ;i--){
        cal_val+=  ((strr[i]=='0') ? w[i] : 0) ;
    }
    return cal_val ;


}

int fill_weighted_value_from_int(int strr, vector<int>&w) {
    int cal_val = 0;
    for(int i = w.size()-1 ; i>=0 ;i--){
        cal_val+=  (( (strr&1) ==0 ) ? w[i] : 0) ;
        strr = strr>>1 ;
    }
    return cal_val ;


}


bool check_symmetrical(int div, map<pair<int,int>,int>&mapp, vector<pair<int,int>>&all_seg, int n_mod){
    for(int i =0 ; i< all_seg.size() ; i++){
        int rotated_x = (all_seg[i].first + div)%n_mod ;
        int rotated_y = (all_seg[i].second + div)%n_mod ;
        if(rotated_y ==0) rotated_y = n_mod ;
        if(rotated_x==0) rotated_x = n_mod ;
        // cout << rotated_x << " "  << rotated_y << " " << div  <<endl ;
        if( mapp[make_pair(rotated_x,rotated_y)] ==0 && mapp[make_pair(rotated_y,rotated_x)]==0 ) return false ;
    }
    return true ;
}





int main(){

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif 
    fast
    string s ;
    cin >> s ;
    int n = s.size() ;
    ll ans =0 ;
    vector<int>mini(n+1,n) ;
    // mini[n-1] = n-2 ;

    for(int i =n-1 ; i>=0 ; i--){
        // only 4 cases are valid start from smallest common difference and go upto cd = 4 ,you will definitely find a match in these 4 case ;
        mini[i] = mini[i+1] ;
        for(int j = 1 ;  (i+2*j) <n ; j++){
            char si = s[i] ;
            char si_k = s[i+j] ;
            char si_2k = s[i+2*j] ;
            ll r = i+2*j ;

            if(si==si_k && si==si_2k) {
                mini[i] = min(mini[i],r) ;
                // cout << i << " " << j <<endl ;
                break ;
                
            }

            

        }
        ans+=n-mini[i] ;
        

    } 
    cout << ans  ;
    

}