<\/strong><\/u><\/a><\/p>\nSolution Approach :<\/h3>\nIntroduction :<\/h4>\n
Idea is to consider every character index, as a vertex of a graph where there is an edge between next and previous indices (vertices) and also between the indices with same values.<\/p>\n
Example : 1213 => string<\/p>\n
By taking indices of the string as vertices, 0–2, 0–1, 1–0, 1–2, 2–3, these are the egdes of the graph. Notice there is a direct edge between 1 (at index 0) and 1(at index 2) as the values in the both indices are same.<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2020\/06\/hopdg.png\")
<\/p>\n
Description :<\/h4>\n
We can use bfs<\/strong> or breadth first search<\/strong> to traverse every vertex, as bfs guarantees the minimum steps (why?, since it moves level wise). As mentioned above we can make a graph with indices as vertices, with every adjacent index and index with same values, as an edge. Additionally, we can store the indices of every character, using a 2-D array with 10 rows (0-9) for values, where each row stores the index of the character with value same as row number.<\/p>\nWe will use visited[]<\/code> array to keep track of the indices which is already visited so we visit every vertex once only. Now we just have to traverse through all the vertices and for every vertex v<\/code> store the distance of every adjacent vertex a<\/code> using distance array distance[]<\/code> as, distance[a]=distance[v]+1<\/code>. <\/p>\nAlgorithms :<\/h3>\n
minDistance()<\/strong> :<\/p>\n\n- \n
create a queue and push the current index now perform following operations untill the queue is empty:<\/p>\n<\/li>\n
- \n
each time we pop a vertex v<\/code> from queue, ( v<\/code> = queue.front() ), we will mark the vertex v<\/code> as visited (visited[v]= true<\/code>).<\/p>\n<\/li>\n- \n
Iterate for all the adjacent vertices of v<\/code> and for every adjacent vertex a<\/code>, do following :<\/p>\n\n- \n
mark a<\/code> as visited and update distance as, distance[a]= distance[v]+1<\/code>.<\/p>\n<\/li>\n- \n
push a<\/code> into the queue.<\/p>\n<\/li>\n- \n
if a<\/code> is not visited,
\nand if parent[v] != a<\/code>. <\/p>\n<\/li>\n- \n
update the ans ( ans = min(ans,current cycle length) ).<\/p>\n<\/li>\n<\/ul>\n<\/li>\n
- \n
Now check if the previous and next index is visited or not, if not mark them as visited and push into the queue.<\/p>\n<\/li>\n<\/ol>\n
Complexity Analysis:<\/h3>\n
The time complexity<\/strong> of the above method is represented in the form of O(V+E)<\/code>, where V<\/code> is the number of verices and E<\/code> is the number of edges. <\/p>\nSolutions:<\/h3>\n
\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645101564020-Article_355.png\")
<\/p>\n