YOSEQ - Digit Subsequence

Given a string consisting of digits from '0' to '9', find the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Input

Input only contains a string S (|S| ≤ 100000), which consists of digits from '0' to '9'.

Output

Output the smallest non-negative integer that does not occur as a contiguous subsequence in the given string.

Example

Input 1
0123456789

Output 1
10
Input 2
21698921085321984125

Output 2
7
Input 3
01234567891011121314151617181920

Output 3
22

Added by:Ahmad Haulian Yoga Pratama
Date:2018-04-20
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SQLITE
Resource:ME

hide comments
2024-02-15 07:51:20
Idea: How many rounds of checking is required? Numbers of 2,3,4 digits... and each number has a starting point... the estimated time complexity is about 10^6*(some small N) only, no TLE... think simple...
2022-07-07 20:49:46 David
STRSEQ is not the same as this problem. This problem is a contiguous subsequence. STRSEQ is subsequence - a much more difficult problem.
2020-08-08 15:42:35
Any hints for this problem?
2018-06-27 13:24:15
good problem:)
2018-06-17 20:54:56 Pranay
http://www.spoj.com/problems/STRSEQ
2018-05-16 08:25:35 hanstan
just brute force will do .-.
2018-05-05 03:18:27
@aditya_rev i think there is a simple adhoc solution
2018-04-30 16:32:01
Any idea for this problem? I've use binary search with some optimazion, but still got TLE._.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.