A runway lighting strip is modeled as a single row of tiles, each tile stamped with one lowercase letter describing its marking. One particular letter marks the strip's anchor lights, and that letter is guaranteed to appear on at least one tile. Ground crews need to know, for every tile, how many tiles away the nearest anchor light sits, measured by index distance along the strip (an anchor tile itself is distance 0 from the nearest anchor light).
s of lowercase English letters (1 <= |s| <= 10^5), the tile markings in order.c, the anchor-light marking. c occurs at least once in s.Print |s| space-separated integers on one line: for each index i of s (0-indexed, left to right), the minimum number of index positions between i and the nearest index j with s[j] == c.
1 <= |s| <= 10^5s consists only of lowercase English letters a-z.c is a single lowercase English letter that occurs at least once in s.Example 1
Input
zzzazzzzazz a
Expected
3 2 1 0 1 2 2 1 0 1 2
Explanation
The anchor letter 'a' sits at indices 3 and 8 of the 11-tile strip. Each tile's distance is the smaller of its distance to index 3 and to index 8: indices 0,1,2 are 3,2,1 away from index 3; index 3 itself is 0; indices 4,5 are 1,2 away from index 3 (closer than to index 8); index 6 is equally 2 away from index 3 as from index 8 (both give 2); index 7 is 1 away from index 8; index 8 is 0; indices 9,10 are 1,2 away from index 8. This gives '3 2 1 0 1 2 2 1 0 1 2'.
Example 2
Input
aqqqa a
Expected
0 1 2 1 0
Explanation
The anchor letter 'a' sits at index 0 and index 4 of the 5-tile strip. Index 0 and index 4 are distance 0; index 1 is 1 away from index 0; index 3 is 1 away from index 4; index 2 is 2 away from both. This gives '0 1 2 1 0'.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →