Skip to Content
CTRL K

Where Am I?

Análisis oficial (C++) 

Explicación

Recorremos todas las longitudes posibles de subcadena kk empezando desde 11. Para cada longitud, usamos un mapa para llevar cuántas veces aparece cada subcadena de longitud kk.

Si todas las subcadenas de esa longitud aparecen solo una vez, sabemos que encontramos la respuesta e imprimimos kk. Esto funciona porque una vez que encontramos una longitud en la que todas las subcadenas son únicas, no hace falta comprobar longitudes mayores.

Implementación

Complejidad temporal: O(N3)\mathcal{O}(N^3)

#include <bits/stdc++.h>
using namespace std;
 
void setIO(string name = "") {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
int main() {
	setIO("whereami");
	int boxes_num;
	string boxes_sequence;
	cin >> boxes_num >> boxes_sequence;
 
	// comprobamos todas las longitudes de subcadena (k) de la más chica a la más grande
	for (int sub_len = 1; sub_len <= boxes_num; sub_len++) {
		bool sol_found = true;
		unordered_map<string, int> sub_frequency;
		// guardamos frecuencias de todas las subcadenas de la longitud dada (sub_len)
		for (int idx = 0; idx <= boxes_num - sub_len; idx++) {
			string sub = boxes_sequence.substr(idx, sub_len);
			sub_frequency[sub]++;
			if (sub_frequency[sub] > 1) { sol_found = false; }
		}
 
		// si todas las subsecuencias son únicas -> encontramos la solución
		if (sol_found) {
			cout << sub_len << endl;
			break;
		}
	}
}
import java.io.*;
import java.util.*;
 
public class WhereAmI {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("whereami");
		int n = io.nextInt();
		String s = io.next();
 
		// probamos cada longitud empezando por la más chica
		for (int guess = 1; guess <= n; guess++) {
			boolean good = true;
			// probamos todas las combinaciones de subcadenas de esa longitud
			for (int i = 0; i + guess <= n; i++) {
				for (int j = 0; j < i; j++) {
					String substring1 = s.substring(i, i + guess);
					String substring2 = s.substring(j, j + guess);
					if (substring1.equals(substring2)) { good = false; }
				}
			}
			if (good) {  // imprimimos la longitud y cortamos porque queremos el
				         // mínimo
				io.println(guess);
				break;
			}
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
file_in = open("whereami.in")
data = file_in.read().strip().split("\n")
n = int(data[0])
mailboxes = data[1]
 
# Inicializamos la respuesta en n, ya que sabemos que n siempre es una respuesta posible
ans = n
 
# Podemos iterar por longitudes de secuencias para encontrar la más chica
for l in range(1, n + 1):
	# Guardamos las subcadenas en un conjunto
	sequences = set()
	for i in range(n - l + 1):
		sequences.add(mailboxes[i : i + l])
	# Comprobamos si todas las subcadenas son únicas
	if len(sequences) == (n - l + 1):
		ans = l
		# Podemos salir del bucle porque esta será la longitud más chica que funciona
		break
 
print(ans, file=open("whereami.out", "w"))
Fundamentos