Intuit OA 2023 - Lost In The Woods

A college passout named Bob is returning to his own college for hiring candidates for the company he works for. Bob is very excited to go back to his college but realizes after entering that his college has changed a lot. After becoming a university, there are a lot of new blocks getting constructed. Bob tries to go to the TnP cell to meet his favorite professor, who is the head of the TnP cell, but there are various obstacles that come in his way. Can you help him meet his favorite professor by guiding him the correct way to roam in the college?

You are given N space-separated characters, the first one represents Bob's current location, and the last one represents the location Bob wants to reach.
There are obstacles in the way represented by *. Bob needs to jump if the next step is an obstacle, and he crosses all adjacent obstacles on jumping.
If there are no obstacles, Bob will walk through the path.

Signals:

• W: Walk
• J: Jump

His favorite professor will not change his location until Bob reaches him! Please guide Bob to the correct path.

Input Format

• The first line contains an integer N, the number of positions.
• The second line contains N space-separated characters representing the path Bob needs to traverse.

Output Format

• A signal string representing the path Bob should take.

Constraints

• The second line contains N space-separated characters (_, *, S, D)
  • '_' represents a clear path.
  • '*' represents an obstacle.
  • 'S' represents the starting point.
  • 'D' represents the destination.

Example

Sample Input:

12
S _ * * _ _ _ * _ * * D

Sample Output:

WJWWJ

Explanation:

Consider 1-based indexing of the given path:
S _ * * _ _ _ * _ * * D

Step-by-step Movement:

1. 1-2: Walk (W)
2. 2-5: Jump over ** to the clear path (J)
3. 5-6: Walk (W)
4. 6-7: Walk (W)
5. 7-9: Jump over * to the clear path (J)
6. 9-12: Jump over ** to reach destination (J)

Thus, the correct signal string is WJWWJ.