Saltar al contenido

Cuente las subcadenas de longitud impar con la mediana igual que el signo K de la cadena

 

#include <bits/stdc++.h>

using namespace std;

 

int sum(int start, int end, vector<int>& v)

{

    

    

    

    unordered_map<int, int> prevSum;

 

    int res = 0, currSum = 0;

 

    for (int i = start; i < end; i++) {

 

        

        currSum += v[i];

 

        

        

        

        if (currSum == 0)

            res++;

 

        if (prevSum.find(currSum) != prevSum.end())

            res += (prevSum[currSum]);

 

        

        

        prevSum[currSum]++;

    }

 

    return res;

}

 

int numberOfSubstrings(string& s, int k)

{

    int n = s.size();

 

    

    

    

    vector<int> smaller(n, 0), greater(n, 0);

    for (int i = 0; i < n; i++) {

        smaller[i] = s[i] < s[k - 1];

 

        greater[i] = s[i] > s[k - 1];

    }

 

    

    

    

    vector<int> diff(n, 0);

    for (int i = 0; i < n; i++)

        diff[i] = smaller[i] - greater[i];

 

    

    int val1 = sum(0, n, diff);

 

    

    int val2 = sum(0, k - 1, diff);

 

    

    int val3 = sum(k, n, diff);

 

    

    

    

    return val1 - val2 - val3;

}

 

int main()

{

    string S = "ecadgg";

    int K = 4;

 

    

    cout << numberOfSubstrings(S, K);

 

    return 0;

}