Chef and Digit Jumps Solution

Problem

Chef loves games! But he likes to invent his own. Now he plays game "Digit Jump". Chef has a sequence of digits $S_{1}, S_{2}, \ldots , S_{N}$. He is staying in the first digit $S_{1}$ and wants to reach the last digit $S_{N}$ in the minimal number of jumps.

While staying in some index $i$ Chef can jump into $i - 1$ and $i + 1$, but he can't jump out from sequence. Or he can jump into any digit with the same value $S_i$.

Help Chef to find the minimal number of jumps he need to reach digit $S_{N}$ from digit $S_1$. 

Input

Input contains a single line consist of string $S$ of length $N$ - the sequence of digits.

Output

In a single line print single integer - the minimal number of jumps he needs.

Constraints

• $1\leq N \leq 10^5$
• Each symbol of $S$ is a digit from $0$ to $9$.

Sample 1:

Input

Output

01234567890

1

Explanation:

Test Case 1: Chef can directly jump from the first digit (it is $0$) to the last (as it is also $0$).

Sample 2:

Input

Output

012134444444443

4

Explanation:

Test Case 2: Chef should follow the following path: $1 - 2 - 4 - 5 - 15$.

Program :

 #include <stdio.h>

#define MAX_N 100000

int N;

int in[MAX_N + 2];

int vis[MAX_N + 2];

int pos[10][MAX_N];

int ans[10];

int q[2*MAX_N + 1];

const int sent = -1;

int main(void)

{

//freopen("input.txt", "r", stdin);

char c;

int d;

for (int i = 0; i < 10; ++i) 

{

ans[i] = 0;

}

N = 0;

vis[0] = 1;

for (N = 1, c = getchar(); c >= '0' && c <= '9'; ++N, c = getchar()) 

{

d = c - 48;

in[N] = d;

vis[N] = 0;

pos[d][ans[d]++] = N;

}

vis[N--] = 1;

int head = 0, tail = 0;

q[tail++] = 1;

q[tail++] = sent;

int path = 0;

int sib;

while (tail< 2*MAX_N) 

{

d = q[head++];

vis[d] = 1;

if (d == sent) 

{

++path;

q[tail++] = sent;

continue;

}

if (d == N) 

{

printf("%d", path);

break;

}

if (vis[d - 1] == 0) {

q[tail++] = d - 1;

vis[d - 1] = 1;

}

if (vis[d + 1] == 0) {

q[tail++] = d + 1;

vis[d + 1] = 1;

}

sib = in[d];

for (int i = ans[sib] - 1; i >= 0; --i) 

{

if (vis[pos[sib][i]] == 0) 

{

q[tail++] = pos[sib][i];

vis[pos[sib][i]] = 1;

}

}

ans[sib] = 0;

}

return 0;

}