USACO 2019 December Contest Bronze Division - Where Am I?

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can solve this by using brute force and check for every length of word to see if all strings are unique.

For further optimizations, we can rely on binary search but this is not necessary. On a more advanced level we can also go for some hashing or string suffix structures but that's more for gold/plat level.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int main()
{
    ifstream cin("whereami.in");
    ofstream cout("whereami.out");

    cin >> n;
    cin >> s;

    for(int len = 1; len <= n; len++)
    {
        set<string> st;
        for(int pos = 0; pos + len - 1 < n; pos++)
        {
            string x;
            for(int j = pos; j < pos + len; j++)
                x += s[j];
            st.insert(x);
        }
        if(st.size() == n - len + 1)
        {
            cout << len;
            return 0;
        }
    }
}

with open("whereami.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
s = tokens[1]
for length in range(1, n+1):
    st = set()
    for pos in range(0, n-length+1):
        x = s[pos:pos+length]
        st.add(x)
    if len(st) == n - length + 1:
        with open("whereami.out", "w") as fout:
            fout.write(str(length))
        exit(0)