P3989 [SHOI2013] Factorial String

shoi2013d1t2 (Note: Be careful with constant factors.)

Given a string $S$ composed of the first $n$ lowercase letters. The string $S$ is a factorial string if and only if every permutation of the first $n$ lowercase letters (in total $n!$ permutations) appears as a subsequence (not necessarily contiguous). From this definition, a simple enumeration can be used to verify it, but it is far too slow. Please design an algorithm to determine within $1$ second whether the given string is a factorial string.

The first line contains an integer $T$, indicating that there are $T$ test cases in this file. Then $T$ blocks follow, each with $2$ lines: - Line $1$: a positive integer $n$, indicating that $S$ is composed of the first $n$ lowercase letters. - Line $2$: a string $s$.

For each test case, output one line: `YES` or `NO`, indicating whether the corresponding string $S$ is a factorial string.

In the first test case, the string `ab` does not appear as a subsequence.  Translated by ChatGPT 5