Concepts Used

Breadth First Search

Difficulty Level

Hard

Problem Statement :

Given a string , we are standing at the starting point and we have to reach end in minimum steps by following these rules:

  • We can either jump to neighbour indices or,
  • We can jump to a position with same value.

See original problem statement here

Solution Approach :

Introduction :

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.

Example : 1213 => string

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.

Description :

We can go through some best websites to learn coding use bfs or breadth first search 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.
We will use visited[] 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 store the distance of every adjacent vertex a using distance array distance[] as, distance[a]=distance[v]+1.

Algorithms :

minDistance() :

  1. create a queue and push the current index now perform following operations untill the queue is empty:
  2. each time we pop a vertex v from queue, ( v = queue.front() ), we will mark the vertex v as visited (visited[v]= true).
  3. Iterate for all the adjacent vertices of v and for every adjacent vertex a, do following :
    • mark a as visited and update distance as, distance[a]= distance[v]+1.
    • push a into the queue.
    • if a is not visited,
      and if parent[v] != a.
    • update the ans ( ans = min(ans,current cycle length) ).
  4. Now check if the previous and next index is visited or not, if not mark them as visited and push into the queue.

Complexity Analysis:

The time complexity of the above method is represented in the form of O(V+E), where V is the number of verices and E is the number of edges.

Solutions:

[TABS_R id=1900]
[forminator_quiz id=”1937″]

Previous post Next Greater Element
Next post Detect Cycle

Leave a Reply

Your email address will not be published. Required fields are marked *