Hop Across Safe Tiles

Medium

A path is laid with tiles, and their state is given as the string tiles: '0' is a sound tile and '1' is a cracked one you must not step on. You start on tile 0, which is always sound. In one jump from tile i you can land on any tile j with i + min_step ≤ j ≤ i + max_step, as long as j is still on the path and tile j is sound. Return True if you can reach the last tile, and False otherwise.

Example 1

tiles="0010100", min_step=2, max_step=3 → True

From tile 0 you can land on 2 or 3; tile 2 is cracked, so go to 3. From tile 3 both 5 and 6 are intact, so jump straight to the last tile, 6.

Example 2

tiles="00110", min_step=1, max_step=1 → False

Every jump is exactly one tile: 0 to 1, and then tile 2 is cracked, so there is no way forward.

Constraints

2 ≤ len(tiles) ≤ 10⁵
tiles contains only '0' and '1'
tiles[0] == '0'
1 ≤ min_step ≤ max_step < len(tiles)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Prefix Sum Sliding Window

Similar problems

Matching Stretch Within Budget Medium Alternate After Rotating Medium Longest Uniform Answer Run Medium Inspecting Three Buildings Medium Trim and Extend a Word Medium

Input

tiles="0010100", min_step=2, max_step=3

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 43 tests on the server, hidden ones included.