We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and forward i.e i-1 and i+1 and jump to any index having the same value as index i.
Time Limit : 1 second
Max input size : 100000

I have tried to solve this problem use a single source shortest path approach using Breadth First Search and though BFS itself is O(V+E) and runs in time the adjacency list creation takes O(n2) time and therefore overall complexity becomes O(n2). is there any way i can decrease the time complexity of adjacency list creation? or is there a better and more efficient way of solving the problem?

int main(){

    vector<int> v;
    string str;
    vector<int> sets[10];

    cin>>str;
    int in;
    for(int i=0;i<str.length();i++){
        in=str[i]-'0';
        v.push_back(in);
        sets[in].push_back(i);
    }

    int n=v.size();
    if(n==1){
        cout<<"0\n";
        return 0;
    }
    if(v[0]==v[n-1]){
        cout<<"1\n";
        return 0;
    }


    vector<int> adj[100001];
    for(int i=0;i<10;i++){
        for(int j=0;j<sets[i].size();j++){
            if(sets[i][j]>0)
                adj[sets[i][j]].push_back(sets[i][j]-1);
            if(sets[i][j]<n-1)  
                adj[sets[i][j]].push_back(sets[i][j]+1);
            for(int k=j+1;k<sets[i].size();k++){
                if(abs(sets[i][j]-sets[i][k])!=1){
                    adj[sets[i][j]].push_back(sets[i][k]);
                    adj[sets[i][k]].push_back(sets[i][j]);
                }
            }
        }
    }

    queue<int> q;
    q.push(0);

    int dist[100001];
    bool visited[100001]={false};
    dist[0]=0;
    visited[0]=true;

    int c=0;
    while(!q.empty()){
        int dq=q.front();
        q.pop();
        c++;

        for(int i=0;i<adj[dq].size();i++){
            if(visited[adj[dq][i]]==false){
                dist[adj[dq][i]]=dist[dq]+1;
                visited[adj[dq][i]]=true;
                q.push(adj[dq][i]);
            }
        }

    }

    cout<<dist[n-1]<<"\n";

    return 0;
}