HackerEarth Superior Substring problem solution

In this HackerEarth Superior Substring problem solution, You are given a string S of length N. If a string contains at least one character whose frequency is greater than or equal to the half of the length of the string, then the string is called superior.

You are required to find the length of the longest superior substring available in the given string S.

HackerEarth Superior Substring problem solution.

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1E5 + 5;
int f[N];
vector<int> A, L, R;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t --) {
        int n;
        string s;
        cin >> n >> s;
        int ans = 1;
        for(int i = 0; i < 26; i ++) {
            int cnt = 0;
            memset(f, 0, sizeof f);
            for(int j = 0; j < n; j ++) {
                if(s[j] - 'a' == i)
                    cnt ++;
                f[j] = cnt;
            }
            for(int j = 0; j < n; j ++) {
                L.push_back((2 * f[j - 1]) - j);
                R.push_back((2 * f[j]) - j);
            }
            int max_len = INT_MIN;
            int min_val = INT_MAX;
            for(int j = 0; j < n; j ++) {
                min_val = min(min_val, L[j]);
                A.push_back(min_val);
                int l = 0, r = j;
                while(l <= r) {
                    int mid = (l + r) >> 1;
                    if(A[mid] <= R[j]) {
                        max_len = max(max_len, j - mid + 1);
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }
            ans = max(ans, max_len);
            A.clear();
            R.clear();
            L.clear();
        }
        cout << ans << 'n';
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 239;

int n, p[M];
string s;
vector<int> q;

void solve()
{
    cin >> n >> s;
    int ans = 0;
    for (char x = 'a'; x <= 'z'; x++)
    {
        q.clear();
        p[0] = 0;
        for (int i = 0; i < n; i++)
        {
            p[i + 1] = p[i];
            if (s[i] == x)
                p[i + 1]++;
            else
                p[i + 1]--;
        }
        q.push_back(n);
        for (int i = n - 1; i >= 0; i--)
        {
            if (p[q.back()] >= p[i] - 1)
            {
                int r = (int)q.size() - 1;
                int l = -1;
                while (r - l > 1)
                {
                    int h = (l + r) / 2;
                    if (p[q[h]] >= p[i] - 1)
                        r = h;
                    else
                        l = h;
                }
                ans = max(ans, q[r] - i);
            }
            if (p[q.back()] < p[i])
                q.push_back(i);
        }
    }
    cout << ans << "n";
}

int main()
{
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--) solve();
}

coding problems solutions