No Time to Paint

#1

I don’t understand why my code is timing out. I calculated my time complexity to be O(26 * n). However, my code timed out on testcases 10 and 13. Is my time complexity anaylsis incorrect?
My approach is standard, calculate the strokes for all the prefixes and suffixes for O(1) time when solving a query.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
typedef long long ll;

int main()
{
    ll n, q;
    cin >> n >> q;
    
    string fence;
    cin >> fence;
    
    fence = '#' + fence;

    ll prefix[n + 1];
    prefix[0] = 0;
    
    ll lastc[27];
    
    lastc[0] = -1;
    for (char c = 'A'; c <= 'Z'; c++) {
        lastc[c - 'A' + 1] = -1;
    }
    
    for (int i = 1; i <= n; i++) {
        char current = fence[i];
        
        bool temp = false;

        if (lastc[current - 'A' + 1] == -1) {
            lastc[current - 'A' + 1] = i;
            prefix[i] = prefix[i - 1] + 1;
            temp = true;
        }
        
        if (!temp) {
            for (char c = 'A'; c < current; c++) {
                if (lastc[c - 'A' + 1] == -1) continue;
                    
                if ((lastc[c - 'A' + 1] > lastc[current - 'A' + 1]) && (lastc[c - 'A' + 1] < i)) {
                    lastc[current - 'A' + 1] = i;
                    prefix[i] = prefix[i - 1] + 1;
                    temp = true;
                    break;
                }
            }
        }
        
        if(!temp) {
            prefix[i] = prefix[i - 1];
            temp = true;
        }
        
        lastc[current - 'A' + 1] = i;
    }

    string fenceReversed = "";
    
    for (int i = n; i >= 1; i--) {
        fenceReversed = fenceReversed + fence[i];
    }
    fenceReversed = '#' + fenceReversed;
    
    
    ll suffix[n + 1];
    suffix[0] = 0;
        
    lastc[0] = -1;
    for (char c = 'A'; c <= 'Z'; c++) {
        lastc[c - 'A' + 1] = -1;
    }
    
    for (int i = 1; i <= n; i++) {
        char current = fenceReversed[i];
        bool temp = false;

        if (lastc[current - 'A' + 1] == -1) {
            lastc[current - 'A' + 1] = i;
            suffix[i] = suffix[i - 1] + 1;

            temp = true;
        }
        
        if (!temp) {
            for (char c = 'A'; c < current; c++) {
                if (lastc[c - 'A' + 1] == -1) continue;
                    
                if ((lastc[c - 'A' + 1] > lastc[current - 'A' + 1]) && (lastc[c - 'A' + 1] < i)) {
                    lastc[current - 'A' + 1] = i;
                    suffix[i] = suffix[i - 1] + 1;
                    temp = true;
                    break;
                }
            }
        }
        
        if(!temp) {
            suffix[i] = suffix[i - 1];
            temp = true;
        }
        
        lastc[current - 'A' + 1] = i;
    }
    
    
    for (int i = 0; i < q; i++) {
        ll x, y;
        cin >> x >> y;
        
        ll sum1 = prefix[x - 1];
        ll sum2 = suffix[n - y];
        
        cout << sum1 + sum2 << endl;
    }
        
}
#2

This code is O(n^2) because you are copying the entire string over and over again:

for (int i = n; i >= 1; i--) {
    fenceReversed = fenceReversed + fence[i];
}

Use the reverse(fence.begin(), fence.end()) function or “+=”.

You have also two blocks of nearly identical code. Write a function for them.

#3

Thanks for that! I didn’t realize that part was O(n^2).