# PATTERNG - Editorial

First, notice the fact that changing the direction of word doesn’t affect the number of individual characters in a row.

In a particular row, the pattern of string that can be possible are-

1)s[x,…,j], some part of a total string, or

2)s[x,…,end] + y * s[start,…,end] + s[start,…z], this can be other row pattern.

For eg, if the word would be CODE, then the 12th row of the pyramid would be:

DECODECODECO = DE + 2 * CODE + CO = s[3,…,end] + 2 * s[start,…,end] + s[1,…,2]

To implement this and to avoid TLE we will implement an array of size (length of string) * 26 to store the frequency of the characters for a particular substring.

Here is the code,

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{

ll row; //height of pyramid
cin >> row;

string str;
cin >> str; //string with which pyramid is made

ll queries;
cin >> queries; //number of queries

ll len = str.length(); //length of string

ll arr[len][26]; //array in which frequency of each character upto a certain height is stored
memset(arr, 0, sizeof(arr));

for (ll i = 0; i < len; i++)
{
arr[i][str[i] - 'A']++;
}

for (ll i = 1; i < len; i++)
{
for (ll j = 0; j < 26; j++)
{
arr[i][j] += arr[i - 1][j];
}
}

while (queries--)
{
ll x;
char ch;
cin >> x >> ch;

ll char_num = 1;

if (x % 2 == 0)
{ //as x can be 10^18 so multiplication is not as such possible
ll a = x / 2;
ll b = x - 1;
a %= len; //so firstly modulus is taken
b %= len;
char_num = (a * b) % len;
}
else
{
ll a = (x - 1) / 2;
ll b = x;
a %= len;
b %= len;
char_num = (a * b) % len;
}

ll ind = (char_num % len) + 1;
ll ans = 0;
ll min_ = min(len - ind, x - 1);
ans += arr[min_ + ind - 1][ch - 'A']; //end substring i.e. s[x,...,end]
if (ind >= 2)
{
ans -= arr[ind - 2][ch - 'A'];
}
x -= (min_ + 1);
ll q = x / len;
ans += q * arr[len - 1][ch - 'A']; //number of strings present i.e. w * s[start,...,end]
q = x % len;

if (q != 0)
ans += arr[q - 1][ch - 'A']; //start of a string i.e. s[start,...,y]

cout << ans << "\n";
}
return 0;
}``````
1 Like