1766B.md (1727B)
1 Source: https://codeforces.com/problemset/problem/1766/B 2 3 B. Notepad# 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You want to type the string $s$, consisting of $n$ lowercase Latin letters, using your favorite text editor Notepad#. 22 23 Notepad# supports two kinds of operations: 24 25 * append any letter to the end of the string; 26 * copy a continuous substring of an already typed string and paste this substring to the end of the string. 27 28 Can you type string $s$ in strictly less than $n$ operations? 29 30 Input 31 32 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 33 34 The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$. 35 36 The second line contains a string $s$, consisting of $n$ lowercase Latin letters. 37 38 The sum of $n$ doesn't exceed $2 \cdot 10^5$ over all testcases. 39 40 Output 41 42 For each testcase, print "YES" if you can type string $s$ in strictly less than $n$ operations. Otherwise, print "NO". 43 44 Example 45 46 Input 47 48 ``` 49 6 50 51 10 52 53 codeforces 54 55 8 56 57 labacaba 58 59 5 60 61 uohhh 62 63 16 64 65 isthissuffixtree 66 67 1 68 69 x 70 71 4 72 73 momo 74 ``` 75 76 Output 77 78 ``` 79 NO 80 YES 81 NO 82 YES 83 NO 84 YES 85 ``` 86 87 Note 88 89 In the first testcase, you can start with typing "codef" ($5$ operations), then copy "o" ($1$ operation) from an already typed part, then finish with typing "rces" ($4$ operations). That will be $10$ operations, which is not strictly less than $n$. There exist other ways to type "codeforces". However, no matter what you do, you can't do less than $n$ operations. 90 91 In the second testcase, you can type "labac" ($5$ operations), then copy "aba" ($1$ operation), finishing the string in $6$ operations.