Sponsored
Sponsored
This approach involves two passe through the string:
c. Calculate the distance from the current index to this recent c.c found on this traversal.This ensures each element in the result is the minimum distance to any occurrence of c.
Time Complexity: O(n), where n is the length of the string since we go through the string twice.
Space Complexity: O(1) additional space for variables, aside from the output array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h>
5
6int*
This solution implements a two-pass approach. We first allocate an array of the same length as the input string to store our results. We use two loops:
c, update prev to this index. Calculate the distance of the current index to prev and store it.prev whenever again the character c is found. Then compute the new distance to the closest c using this prev and update the result if necessary.