The problem requires determining if a sequence of tasks, represented by uppercase letters, violates a specific constraint: once a task is abandoned for a different one, it cannot be resumed. In terms of the string representation, this means no character can reappear after a different character has been encountered.

Approach

A straightforward method involves iterating through the string while keeping track of characters that have been completely processed. We maintain a boolean array to record characters that have been "seen" and subsequently changed. As we process each character:

• If the current character is the same as the previous one, the task is ongoing, and no rule is broken.
• If the current character differs from the previous one, we check if the current character has already been marked as seen. If it has, it implies a return to a previous task, making the sequence invalid.
• If it hasn't been seen, we mark the previous character as seen and update our tracking variable to the current character.

Complexity

• Time Complexity: O(n) per test case, where n is the length of the string, since we process each character exactly once.
• Space Complexity: O(1), as the boolean array size is fixed at 26 for the Latin alphabet.

Implementation

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int total_tests;
    cin >> total_tests;
    
    while (total_tests--) {
        int length;
        string tasks;
        cin >> length >> tasks;
        
        vector<bool> visited(26, false);
        bool is_suspicious = false;
        char prev_task = '\0';
        
        for (char curr_task : tasks) {
            if (curr_task != prev_task) {
                if (visited[curr_task - 'A']) {
                    is_suspicious = true;
                    break;
                }
                if (prev_task != '\0') {
                    visited[prev_task - 'A'] = true;
                }
                prev_task = curr_task;
            }
        }
        
        cout << (is_suspicious ? "NO" : "YES") << endl;
    }
    
    return 0;
}