HIIT Generation

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>

using namespace std;


int main() {
    int n;
    cin >> n;

    char l[4] = {'H', 'I', 'I', 'T'};

    int *transf = new int[n + 1];
    int *letter = new int[n + 1];
    int transf_p = 0;
    int letter_p = 0;
    transf[0] = -1;
    letter[0] = 0;

    int last_i = -1, last_h = -1, last_t = -1;

    char *c = new char[n];
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        c[i] = ch;
        if (ch == 'H') last_h = i;
        if (ch == 'I') last_i = i;
        else last_t = i;
    }
    int last[4] = {last_h, last_i, last_i, last_t};
    while (transf_p >= 0) {
        int t_id = transf[transf_p];
        int letter_id = letter[letter_p];
        char c_to_be_printed = l[letter_id];

        // cout << "t_id " << t_id << " letter " << c_to_be_printed << endl;

        bool addTransf = false;
        if (t_id + 1 <= last[letter_id]) {
        for (int next_t_id = t_id + 1; next_t_id < n; next_t_id++) {
            // cout << " trying to apply transform " << next_t_id << endl;
            if (c[next_t_id] == c_to_be_printed) { // if this transformation will apply to the letter
                // cout << "add transformation " << next_t_id << endl;
                if (letter_id == 3) {letter_p--; transf_p--;}
                else letter[letter_p] = letter_id + 1;

                transf[++transf_p] = next_t_id;
                letter[++letter_p] = 0;
                addTransf = true;
                break;
            }
        }
        }
        if (!addTransf) {
            // cout << "print ";
            cout << c_to_be_printed;
            if (letter_id == 3) {letter_p--; transf_p--;}
            else letter[letter_p] = letter_id + 1;
        }
    }
    cout << endl;

    delete[] c;
    delete[] transf;
    delete[] letter;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED