A loading-dock scanner appends one lowercase letter to a running trail every time a pallet rolls past a checkpoint, the letter being that pallet's code, in the order the pallets passed. Whenever the same code appears at two different positions i < j in the current trail, the dock supervisor may erase the earlier entry (the one at position i) — not necessarily the closest such earlier entry, any earlier duplicate of the same letter qualifies. After an erasure the remaining letters keep their relative order and are simply renumbered, and the supervisor may repeat this erasure operation any number of times, choosing a fresh pair of matching positions each time. Determine the minimum length the trail can be reduced to.
One line containing the trail string s: only lowercase English letters, with 1 <= length of s <= 100.
One integer: the minimum length the trail can be reduced to.
Example 1
Input
tomato
Expected
4
Explanation
The letters that appear, in order, are t, o, m, a, t, o. The extra earlier copies (the 't' at index 0 and the 'o' at index 1) can each be erased once their later duplicate exists (index 4 for 't', index 5 for 'o'), leaving one t, one o, one m, and one a: length 4. The trail can never drop below 4, since erasure only ever removes an earlier copy and can never remove the single surviving instance of a letter, so at least one copy of each distinct letter (t, o, m, a) must always remain.
Example 2
Input
abcabc
Expected
3
Explanation
The letters are a, b, c, a, b, c: 3 distinct letters (a, b, c). The earlier a, b, and c at indices 0-2 can each be erased against their later duplicate at indices 3-5, leaving length 3, which is also the floor since each of the 3 distinct letters must keep at least one surviving copy.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →