Funcia
Lv.1arraystringtwo-pointers

Distance to the Nearest Stop

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

road is a string of lowercase letters; cells marked with the character c are bus stops. For every index i, compute the distance |i - j| to the nearest index j with road[j] == c, and return the distances in order. c appears in road at least once.

Examples

roadcresult
"loveleetcode"'e'[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
"aaab"'b'[3, 2, 1, 0]
"x"'x'[0]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(road: string, c: char) → int[]

Constraints

  • 1≤1 \le road.length ≤200,000\le 200{,}000, lowercase English letters only
  • c is a lowercase letter that appears in road at least once

Expected complexity

Time
O(N)
Space
O(N)

Examples

roadcExpected
"loveleetcode""e"[3,2,1,0,1,0,0,1,2,2,1,0]
"aaab""b"[3,2,1,0]
"x""x"[0]

Hint

Hint

The nearest stop is either the last one to the left or the first one to the right. One left-to-right pass gives the distance to the left stop, one right-to-left pass gives the distance to the right stop; take the minimum. Searching outward from every cell is O(N2)O(N^2) when stops are rare and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251142 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.