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
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 |
RSS