Count of Numbers in a Range where digit d occurs exactly K times

#include <bits/stdc++.h>

using namespace std;

#define N 100

  

void pre_process(bool dp[N][N], string s)

{

  

    

    int n = s.size();

  

    

    

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

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

            dp[i][j] = false;

    }

  

    

    for (int j = 1; j <= n; j++) {

  

        

        

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

  

            

            if (j <= 2) {

  

                

                if (s[i] == s[i + j - 1])

                    dp[i][i + j - 1] = true;

            }

  

            

            else if (s[i] == s[i + j - 1])

                dp[i][i + j - 1] = dp[i + 1][i + j - 2];

        }

    }

}

  

int countPairs(string s)

{

  

    

    bool dp[N][N];

    pre_process(dp, s);

    int n = s.length();

  

    

    int left[n];

    memset(left, 0, sizeof left);

  

    

    int right[n];

    memset(right, 0, sizeof right);

  

    

    left[0] = 1;

  

    

    

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

  

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

  

            if (dp[j][i] == 1)

                left[i]++;

        }

    }

  

    

    right[n - 1] = 1;

  

    

    

    for (int i = n - 2; i >= 0; i--) {

  

        right[i] = right[i + 1];

  

        for (int j = n - 1; j >= i; j--) {

  

            if (dp[i][j] == 1)

                right[i]++;

        }

    }

  

    int ans = 0;

  

    

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

        ans += left[i] * right[i + 1];

  

    return ans;

}

  

int main()

{

    string s = "abacaba";

    cout << countPairs(s);

  

    return 0;

}