Author: Soumy
Tester: Divyank
Editorialist: Lakshay
DIFFICULTY:
EASY, MEDIUM.
PREREQUISITES:
Greedy.
EXPLANATION:
A string is said to be a cutie string if it is a substring of a given string and appears at least twice in a given string, so to solve this problem we can generate each substring of a given string and store its count in a map data structure and then taken a maximum of the length of that substring which appears at least twice.
See code for better understanding.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace pb_ds;
//
// template<typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// clang-format off
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
// clang-format on
void work()
{
ll n;
cin >> n;
string s;
cin >> s;
ll ans = 0;
map<string, ll> M;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
string t = s.substr(i, j - i + 1);
M[t]++;
if (M[t] > 1)
ans = max(ans, (ll)t.size());
}
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin>>t;
while (t--)
{
work();
}
return 0;
}