Earliest Coordinate Reach with Optional Moves

Given a string of directions and start/end coordinates, return the earliest second at which the target can be reached if each second allows either taking the indicated move or staying still. Requirements Input: directions: a string of length n over E, S, W, N. (startX, startY) and (endX, endY). At second i, choose either to move one unit in direction directions[i] or to stay in place. Return the earliest time at which the target coordinate can be reached. If the target cannot be reached within n seconds, return -1. Direction mapping: E: (x + 1, y) S: (x, y - 1) W: (x - 1, y) N: (x, y + 1) Examples directions = "WWNNSSE" startX = 1 startY = -1 endX = -1 endY = -1 Output: 6 Notes A direct DP over all reachable coordinates works but can run out of memory on larger hidden tests. A lighter check scans prefixes: after i moves, count how many E/W/N/S moves are available in the prefix, then decide whether the required delta from start to target can be formed by selecting a subset of those moves. Binary search over the earliest prefix length is viable if the feasibility predicate is monotonic. The main trap is treating each direction as mandatory; every step is optional. Preparation Derive the prefix feasibility check on paper: required east/west and north/south moves must be covered by available directional counts, and unused prefix moves can be skipped. Implement a linear scan first, then add a binary-search wrapper only after proving the predicate is monotonic over prefix length.