Because N is at most 100, one approach that comes to mind is checking if K=1 is valid. If so, then the answer is 1 and we can stop. Otherwise, we check if K=2 is valid. We'll keep on increasing K until it reaches N, as K=N is guaranteed to be valid.
How do we check if a given value of K is valid? We can loop over all pairs of substrings of length K and compare them for equality. My code following this approach is as follows:
#include <iostream> using namespace std; int main() { freopen("whereami.in", "r", stdin); freopen("whereami.out", "w", stdout); int n; string s; cin >> n >> s; for(int guess = 1; guess <= n; guess++) { bool good = true; for(int i = 0; i + guess <= n; i++) { for(int j = 0; j < i; j++) { if(s.substr(i, guess) == s.substr(j, guess)) { good = false; } } } if(good) { cout << guess << "\n"; break; } } }
It is possible to do faster by using a data structure known as a set. Sets cannot store duplicate elements but are able to quickly identify if a given element is already part of the set. Therefore, to check if a given value of K is valid using a set, we can check if a substring is present in the set before inserting it. If some substring is already present, then the given value of K is invalid.
Here is Brian Dean's solution using a set.
#include <iostream> #include <fstream> #include <string> #include <set> using namespace std; int N; string S; bool dups(int len) { set<string> X; for (int i=0; i<=N-len; i++) { if (X.count(S.substr(i,len)) > 0) return true; X.insert(S.substr(i,len)); } return false; } int main(void) { ifstream fin ("whereami.in"); ofstream fout ("whereami.out"); fin >> N >> S; int ans = 1; while (dups(ans)) ans++; fout << ans << "\n"; return 0; }