Skip to Content
CTRL K

They are Everywhere

Editorial oficial 

Solución

Explicación

Iteramos por todos los departamentos posibles de fin manteniendo una variable (\texttt{closest\\_left} en el código) que lleva el punto de inicio más cercano. Al movernos uno hacia la derecha, primero agregamos el nuevo Pokémon a nuestra lista de Pokémon atrapados. Luego, mientras el Pokémon del punto de inicio no sea único, movemos el punto de inicio un departamento hacia adelante. Tras procesar cada punto de fin, actualizamos el mínimo total de departamentos recorridos.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int flat_num;
	std::cin >> flat_num;
	vector<char> flats(flat_num);
	std::unordered_set<char> types;
	for (char &p : flats) {
		std::cin >> p;
		types.insert(p);
	}
 
	int shortest_interval = INT32_MAX;
	std::unordered_map<char, int> curr_pokemon;
	int closest_left = 0;
	for (int right = 0; right < flat_num; right++) {
		curr_pokemon[flats[right]]++;
		// chequeamos si sacar el de la izquierda eliminaría un tipo necesario
		while (closest_left + 1 <= right && curr_pokemon.count(flats[closest_left]) &&
		       curr_pokemon[flats[closest_left]] > 1) {
			curr_pokemon[flats[closest_left]]--;
			closest_left++;
		}
		/*
		 * por supuesto, es posible que la configuración actual
		 * no fuera válida en absoluto, así que hay que chequearlo
		 */
		if (curr_pokemon.size() == types.size()) {
			shortest_interval = std::min(shortest_interval, right - closest_left + 1);
		}
	}
	cout << shortest_interval << endl;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
 
public class Everywhere {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int flatNum = Integer.parseInt(read.readLine());
		String flats = read.readLine();
 
		HashSet<Character> types = new HashSet<>();
		for (int f = 0; f < flatNum; f++) { types.add(flats.charAt(f)); }
 
		int shortestInterval = Integer.MAX_VALUE;
		int closestLeft = 0;
		HashMap<Character, Integer> currCaught = new HashMap<>();
		for (int right = 0; right < flatNum; right++) {
			char newCaught = flats.charAt(right);
			currCaught.put(newCaught, currCaught.getOrDefault(newCaught, 0) + 1);
			// movemos el puntero izquierdo solo si no es único
			while (closestLeft + 1 <= right &&
			       currCaught.getOrDefault(flats.charAt(closestLeft), 0) > 1) {
				currCaught.put(flats.charAt(closestLeft),
				               currCaught.get(flats.charAt(closestLeft)) - 1);
				closestLeft++;
			}
			/*
			 * por supuesto, podría ser que la configuración no fuera válida
			 * de entrada, así que hay que chequearlo
			 */
			if (currCaught.size() == types.size()) {
				shortestInterval = Math.min(shortestInterval, right - closestLeft + 1);
			}
		}
		System.out.println(shortestInterval);
	}
}
flat_num = int(input())
flats = input()
types = set(flats)
 
shortest_interval = float("inf")
closest_left = 0
curr_caught = {}
for right, f in enumerate(flats):
	if f not in curr_caught:
		curr_caught[f] = 0
	curr_caught[f] += 1
 
	# movemos el puntero izquierdo solo si ya atrapamos otro igual
	while closest_left + 1 <= right and curr_caught.get(flats[closest_left], 0) > 1:
		curr_caught[flats[closest_left]] -= 1
		closest_left += 1
 
	"""
	por supuesto, podría ser que la configuración no fuera válida de entrada,
	así que hay que chequearlo
	"""
	if len(curr_caught) == len(types):
		shortest_interval = min(shortest_interval, right - closest_left + 1)
 
print(shortest_interval)
Fundamentos