Approach #1: Min Array [Accepted]

Intuition

For each index S[i], let's try to find the distance to the next character C going left, and going right. The answer is the minimum of these two values.

Algorithm

When going left to right, we'll remember the index prev of the last character C we've seen. Then the answer is i - prev.

When going right to left, we'll remember the index prev of the last character C we've seen. Then the answer is prev - i.

We take the minimum of these two answers to create our final answer.

Complexity Analysis

  • Time Complexity: , where is the length of S. We scan through the string twice.

  • Space Complexity: , the size of ans.


Analysis written by: @awice.