Algorithm
You want to type the string s, consisting of n lowercase Latin letters, using your favorite text editor Notepad#.
Notepad# supports two kinds of operations:
- append any letter to the end of the string;
- copy a continuous substring of an already typed string and paste this substring to the end of the string.
Can you type string s in strictly less than n operations?
The first line contains a single integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains a single integer n (1≤n≤2⋅105) — the length of the string s.
The second line contains a string s, consisting of n lowercase Latin letters.
The sum of n doesn't exceed 2⋅105 over all testcases.
For each testcase, print "YES" if you can type string s in strictly less than n operations. Otherwise, print "NO".
NO YES NO YES NO YES
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.
In the second testcase, you can type "labac" (5 operations), then copy "aba" (1 operation), finishing the string in 6 operations.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define debug(n) cout<<(n)<<endl;
#define pb push_back
const ll INF = 2e18 + 99;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
bool flag = false;
int n;
cin>>n;
map<string, int> mp;
string s;
cin>>s;
string a;
for(int i = 1; i < n; i++){
a = "";
a += s[i-1];
a += s[i];
if(mp.find(a) != mp.end() && mp[a] < i-1){
flag = true;
break;
}
else if(mp.find(a) == mp.end()){
mp[a] = i;
}
}
if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl;
}
}Input
10
codeforces
8
labacaba
5
uohhh
16
isthissuffixtree
1
x
4
momo
Output
YES
NO
YES
NO
YES
Demonstration
Codeforcess Solution 1766-B B. Notepad# ,C++, Java, Js and Python,1766-B,Codeforcess Solution