A - Divide String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の英小文字からなる文字列 S が与えられます。S を 2 個以上の連続部分文字列に分割し、それらが辞書順で狭義単調増加になるようにすることが出来るか判定してください。

厳密に書くと、以下の条件を全て満たす文字列の列 t=(t_1,t_2,\dots,t_k) が存在するか判定してください。

  • 列の長さ k は 2 以上である。

  • t_i は空でない。(1 \le i \le k)

  • t_1,t_2,\dots,t_k をこの順で連結すると S と一致する。

  • 1 \le i < k を満たす整数 i に対して、t_i は t_{i+1} より辞書順で小さい。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

辞書順とは？

文字列 S = S_1S_2\ldots S_{|S|} が文字列 T = T_1T_2\ldots T_{|T|} より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。

  1. |S| \lt |T| かつ S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}。
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}
    • S_i が T_i よりアルファベット順で小さい文字である。

制約

  • 1 \le T \le 2000
  • 2 \le N \le 2000
  • S は長さ N の英小文字からなる文字列
  • 1 個の入力に含まれるテストケースについて、それらの N の総和は 2000 を超えない。

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで、\mathrm{case}_i とは i 個目のテストケースである。各テストケースは以下の形式で与えられる。

N
S

出力

T 行出力せよ。

i(1 \le i \le T) 行目には、i 個目のテストケースにおいて S を条件を満たすように分割できるならば Yes を、そうでないならば No を出力せよ。

入力例 1

5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

出力例 1

Yes
No
Yes
Yes
No

1 個目のテストケースは、S を a,ba,c と分割すればよいです。

2 個目のテストケースは、S をどのように分割しても辞書順で狭義単調増加にすることは出来ません。

Score : 300 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Determine whether it is possible to divide S into two or more consecutive substrings so that they are strictly increasing in lexicographical order.

To be precise, determine whether there is a sequence of strings t=(t_1,t_2,\dots,t_k) that satisfies all of the following conditions.

  • The length of the sequence k is at least 2.

  • t_i is not empty. (1 \le i \le k)

  • Concatenating t_1,t_2,\dots,t_k in this order results in S.

  • t_i is lexicographically smaller than t_{i+1} for every integer i such that 1 \le i < k.

You are given T test cases. Find the answer for each of them.

What is lexicographical order?

A string S = S_1S_2\ldots S_{|S|} is said to be lexicographically smaller than a string T = T_1T_2\ldots T_{|T|} if either 1. or 2. below holds. Here, |S| and |T| represent the lengths of S and T, respectively.

  1. |S| \lt |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold.
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
    • The character S_i comes before T_i in alphabetical order.

Constraints

  • 1 \le T \le 2000
  • 2 \le N \le 2000
  • S is a string of length N consisting of lowercase English letters.
  • The sum of N over all test cases in a single input does not exceed 2000.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Here, \mathrm{case}_i represents the i-th test case. Each test case is given in the following format:

N
S

Output

Print T lines.

The i-th line (1 \le i \le T) should contain Yes if it is possible to divide S in the i-th test case into substrings that satisfy the conditions, and No otherwise.

Sample Input 1

5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

Sample Output 1

Yes
No
Yes
Yes
No

For the first test case, you can divide S into a, ba, c.

For the second test case, there is no way to divide S into substrings so that they are strictly increasing in lexicographical order.