codeforces#P2200C. Specialty String
-
ID: 42023
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Specialty String
Problem Description
AksLolCoding is playing a game on a string $s$ of length $n$. Initially, $s$ contains only lowercase Latin characters.
In one turn, AksLolCoding can choose any pair of integers $(i,j)$ such that:
- $1 \leq i \lt j \leq n$;
- $s_i = s_j \neq *$; and
- $s_k = *$ for all $i \lt k \lt j$.
Once the game ends, AksLolCoding wins if and only if every character in $s$ is equal to $*$. Determine if it is possible for AksLolCoding to win.
Note: $*$ represents ASCII character 42.
The first line contains an integer $t$ ($1 \leq t \leq 100$), the number of test cases.
The first line of each test case contains an integer $n$ ($1 \leq n \leq 5000$), the length of the string.
The second line of each test case contains a string $s$ consisting of lowercase Latin characters.
The sum of $n$ over all test cases does not exceed $5000$.
Output the answer to each test case on its own line. If AksLolCoding can win, output "YES" (without quotes). Else, output "NO" (without quotes).
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
Input Format
The first line contains an integer $t$ ($1 \leq t \leq 100$), the number of test cases.
The first line of each test case contains an integer $n$ ($1 \leq n \leq 5000$), the length of the string.
The second line of each test case contains a string $s$ consisting of lowercase Latin characters.
The sum of $n$ over all test cases does not exceed $5000$.
Output Format
Output the answer to each test case on its own line. If AksLolCoding can win, output "YES" (without quotes). Else, output "NO" (without quotes).
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
6
1
a
6
llmllm
6
uwuuwu
6
byebye
6
oooioi
12
siixxsevvenn
,
NO
YES
YES
NO
NO
YES
Hint
In the first test case, it can be shown that it is impossible for AksLolCoding to win.
In the second test case, AksLolCoding can win by making the following moves: llmllm $\rightarrow$ llm**m $\rightarrow$ **m**m $\rightarrow$ ******
In the third test case, AksLolCoding can win by making the following moves: uwuuwu $\rightarrow$ uw**wu $\rightarrow$ u****u $\rightarrow$ ******