I am solving this question using bfs as propsed in editorial, but I am not getting how the adjacency list will be generated for this graph.

Link to the Editorial

I am solving this question using bfs as propsed in editorial, but I am not getting how the adjacency list will be generated for this graph.

Link to the Editorial

The adjacency list that you will use will be as follows :

vector **graph[n]**; //This is basically an array of n cells, each cell having it’s data type as a vector.

You iterate a variable **i** from 1 to **n**. For every index i, you push_back Si+1, Si-1, and all those indexes j such that Si == Sj into graph[i].

This way, you get the all possible adjacent nodes to a node i, in the vector **graph[i]**.

1 Like

If suppose I have 5 on the first index and also 5 on the 5^{th} index then index 5 should be there in adjacency list of 1. Ho this situation will be taken care of.

1 Like

@arpit728 : I dont think you actually need to build the graph. Just store indexes of each digit . Refer this if you still don’t understand.

I got you n that for every index i push s_{i-1} and s_{i+1} into its adjacency list but to find si==sj I will have to iterate through all graph again and will increase the complexity.

@ankg has explained quite nicely but if you want to look at implementation for reference here’s the link