CF - They are Everywhere

Author: Kevin Sheng

Appears In

Silver - Two Pointers

Explanation

Let's iterate through all possible ending flats while keeping a variable ( $\texttt{closest\_left}$ in the code) that keeps track of the closest starting point. When moving one to the right, we first add the new Pokemon to our list of caught Pokemon. Then, as long as the Pokemon at the starting point isn't unique, we move the starting point one flat forward. After processing each ending point, we update the total minimum flats travelled.

Implementation

Time Complexity: $\mathcal{O}(N)$

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;

/**
 * https://codeforces.com/problemset/problem/701/C
 * 7
 * bcAAcbc should output 3

Python

"""
https://codeforces.com/contest/701/problem/C
7
bcAAcbc should output 3
6
aaBCCe should output 5
"""
flat_num = int(input())
flats = input()
types = set(flats)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!