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 5th 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 si-1 and si+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