My Logic is working for smaller input How can I make it better to accepts for larger inputs.

Q)
The program must accept a string S containing only lower case alphabets and Q queries as the input. Each query contains two integers representing the starting and the ending indices of a substring in S. For each query, the program must print the most frequently occurring alphabet in the specified substring. If two or more alphabets have the same frequency, then the program must print the alphabet that is least in the alphabetical order.

Boundary Condition(s):
2 <= Length of S <= 1000
1 <= Q <= 10^5

Example :
Input: badbadbed
4
0 8
1 4
0 5
2 7
Output:
b
a
a
b

#include <bits/stdc  .h>
using namespace std;
int main(int argc, char** argv)
{
string s;
cin>>s;
int k;
cin>>k;
int x,y;
while(k--)
{
cin>>x>>y;
map<char, int>counter;
string ss=s. substr(x,y-x 1);
set <char>sample;
for(auto i:ss)
sample.insert(i);
int maxx=-1, st; char anss;
for(auto i: sample)
if((st=count(ss.begin(),ss.end(), i))>maxx)
{
maxx=st;
anss=i;
}
cout<<anss<<endl;
}
}

CodePudding user response：

Following code has a lot of memory waste, but each query is looked up in O(1):

int main() {
    std::string s;
    int q = 0, start = 0, end = 0;
    std::cin >> s;
    std::cin >> q;

    auto mem = std::make_unique<int[]>(26 * s.length());
    for (int i = 0; i < s.length(); i  ) {
        mem[i * 26   s[i] - 'a']  ;
        if (i < (s.length()-1)) {
            for (int l = 0; l < 26; l  ) {
                mem[(i 1) * 26   l] = mem[i * 26   l];
            }
        }
    }

    for (int i = 0; i < q; i  ) {
        std::cin >> start >> end;
        int max_val = 0;
        int max_idx = -1;
        for (int l = 0; l < 26; l  ) {
            auto v = (mem[end * 26   l] - mem[start * 26   l]);
            if (v > max_val) {
                max_val = v;
                max_idx = l;
            }
        }

        std::cout << (char)('a'   max_idx) << std::endl;
    }

    return 0;
}

CodePudding user response：

Have you ever heard of segment trees?

Usually, when encountered with problems regarding some kind of value on an interval, we usually deploy segment trees to deal with these types of problems. The tree gives n*log(n) complexity, very niceeee, I love them so muchy much :)

Please stop reading if you haven't heard of recursion/segment tree/map/ yet.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time

First of all, instead of considering the most frequently occurring alphabet, let us consider the occurrence of all characters of the full string. If we have the occurrence of all characters, we can easily pick out the one that has the most occurrences.

Great, let's look at the operation you'll need:

1. Build a segment tree from the string
2. Query the interval from the segment tree

If you look at the usual segment tree implementations on the internet, they're usually about the maximum or minimum value over an interval, so they'll build their segment using std::max(...).

In our case, we care about the occurrence of all characters, so we'll build our segment using the whole alphabet (only 26 lol)

void build(int id, int l, int r, std::string str, std::vector<std::map<char, int>>& seg_tree) 
{
    if(l == r) {
        seg_tree[id][str[l]]  ;
        return;
    }
    int mid = (l r)/2;

    build(id*2, l, mid, str, seg_tree);
    build(id*2 1, mid 1, r, str, seg_tree);

    for(int i=97;i<=122;i  ) {
        seg_tree[id][(char)i] = seg_tree[id*2][(char)i]   seg_tree[id*2 1][(char)i];
    }
    return;
}

The query follows the same format, we'll recursively descend into the tree until we have an interval of 1, then we'll go back up to to combine smaller queries into bigger queries.

std::map<char, int> query(int id, int l, int r, int q, int p, std::vector<std::map<char, int>>& seg_tree) {
    std::map<char,int> mp;
    if(p < l || q > r) {
        return mp;
    }

    if(l <= q && p <= r) {
        return seg_tree[id];
    }

    int mid = (l r)/2;

    std::map<char,int> mp1 = query(id*2, l, mid, q, p, seg_tree);
    std::map<char,int> mp2 = query(id*2 1,mid 1, r, q, p, seg_tree);

    for(int i=97;i<=122;i  ) {
        mp[(char)i] = mp1[(char)i]   mp2[(char)i];
    }

    return mp;
}

And then, here's the general idea on how to use the segment tree

int main() {
    std::string str;
    std::cin >> str;
    
    
    std::vector<std::map<char, int>> seg_tree(4*str.size() 1);
    
    build(1,0,str.size()-1,str,seg_tree);

    std::map<char, int> mp = query(1, 0, str.size()-1, 0,str.size()-1, seg_tree);

    std::cout << mp.size() << std::endl;


    for(int i=97;i<=122;i  ) {
        std::cout << (char)i << " " << mp[(char)i] << std::endl;
    }
    return 0;
}

Knowing the segment tree data structure helps you a lot in competitive programming or even in coding interviews.

Please give me more feedback on how to answer your question or explain my answer better :)