Let's say you're given a string where the start point is the beginning of the string and the end point is the end of the string. For each turn, you can jump at most s positions in the string but there are obstacles in the string which you are not allowed to land on.

So for example a string like "SOOOXOE" (where "O" represents a free space and "X" represents an obstacle) and there's an s value of 3. The minimum number of moves in this case to get from S to E is 2. But in a case like "SOOOXXOE" with the same s value, the minimum number of moves is 3.

I came up with a greedy where you jump as far as possible as long as it's valid position each turn and it works. But I need to calculate the minimum number where the difference between S and E is at most 1,000,000,000 so simulating the jumping is too slow. Does anyone have any ideas about how to solve this efficiently?

*Note that I'm not actually given a string of length 1,000,000,000 but I visualized it as a string so it's easier to understand. Also if it helps, there will be at most 40 obstacles per string and s is always greater than 1 and less than or equal to 6. It is always possible to reach E from S.