Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
17
Indexable
#include <bits/stdc++.h>
using namespace std;

#define int long long

bool f(int len,int n,int*left_,int*right_){
    if(len == 0)return true;
    if(2*len > n)return false;
    for(int i=0;i + (2*len)  - 1 < n;i++){
        int left_c = left_[i + len - 1] - (i > 0 ? left_[i-1] : 0);
        int right_c = right_[i + 2*len - 1] - right_[i + len - 1];
        if((left_c == right_c) && (left_c == len))return true;
    }
    return false;
}


void solve(){
    int n;cin>>n;
    string st;
    cin>>st;
    int left_[n];
    int right_[n];
    memset(left_,0,sizeof(left_));
    memset(right_,0,sizeof(right_));
    if(st[0] == '<')left_[0] = 1;
    for(int i=1;i<n;i++){
        left_[i] = left_[i-1];
        if((st[i] == '<') || (st[i] == '?'))left_[i]++;
    }

    if(st[0] == '>')right_[0] = 1;
    for(int i=1;i<n;i++){
        right_[i] = right_[i-1];
        if(st[i] == '>' || st[i] == '?')right_[i]++;
    }
 
    


    int low = -1;
    int high = (n + 1)/2;
    int mid;

    while(low + 1 < high){
        mid = (high + low)/2;
        if(f(mid,n,left_,right_) == true){
            low = mid;
        }else high = mid;
    }

    cout<<2*low<<endl;


}

int32_t main(){
    int t;cin>>t;
    while(t--)solve();
    
}
Editor is loading...
Leave a Comment