YOSEQ - Digit Subsequence

no tags 

Given a string consisting of numbers 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 numbers 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

hide comments
slothsphereoj: 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...

David: 2022-07-07 20:49:46

STRSEQ is not the same as this problem. This problem is a contiguous subsequence. STRSEQ is subsequence - a much more difficult problem.

night_rider: 2020-08-08 15:42:35

Any hints for this problem?

be1035016: 2018-06-27 13:24:15

good problem:)

Pranay: 2018-06-17 20:54:56

http://www.spoj.com/problems/STRSEQ

hanstan: 2018-05-16 08:25:35

just brute force will do .-.

boemogensen: 2018-05-05 03:18:27

@aditya_rev i think there is a simple adhoc solution

aditya_rev: 2018-04-30 16:32:01

Any idea for this problem? I've use binary search with some optimazion, but still got TLE._.


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