Dada una cadena S y un carácter C, retornar un arreglo de enteros representando la distancia más corta desde cada carácter en la cadena hasta una ocurrencia del carácter C.

Ejemplo 1:

Entrada: “algoritmo”, ‘o’

Salida: [3, 2, 1, 0, 1, 2, 2, 1, 0]

Ejemplo 2:

Entrada: “abcdefga”, ‘a’

Salida: [0, 1, 2, 3, 3, 2, 1, 0]

Precondiciones:

La longitud de S está en [1, 1000].

C es un único carácter.

C se encuentra en S.

Todas las letras en S y C son minúsculas.

Solución intuitiva:

Por cada índice S[i], se intenta encontrar la distancia al siguiente carácter C yendo hacia la iziquierda y yendo hacia la derecha. La respuesta será el menor de esos dos valores.

Algoritmo:

Yendo de izquierda a derecha, guardar el índice prev del último carácter C encontrado. Así, la respuesta será i - prev.

Yendo de derecha a izquierda, guardar el índice prev del último carácter C encontrado. Así, la respuesta será prev - i.

Tomar el menor de estos dos valores para obtener el resultado final.

Complejidad:

De tiempo: O(N), donde N es la longitud de S. Se pasa dos veces por toda la cadena.

De espacio: O(N), el tamaño de la respuesta.

Solución en Python:

def distanciaMasCorta(S, C):
    prev = float('-inf')
    ans = []
    for i, x in enumerate(S):
        if x == C:
            prev = i
        ans.append(i - prev)
    prev = float('inf')
    for i in range(len(S) - 1, -1, -1):
        if S[i] == C:
            prev = i
        ans[i] = min(ans[i], prev - i)
    return ans

Solución en Java:

public int[] distanciaMasCorta(String S, char C) {
	int N = S.length();
	int[] ans = new int[N];
	int prev = -(S.length()+1);

	for (int i = 0; i < N; ++i) {
		if (S.charAt(i) == C)
			prev = i;
		ans[i] = i - prev;
	}

	prev = S.length()+1;
	for (int i = N-1; i >= 0; --i) {
		if (S.charAt(i) == C)
			prev = i;
		ans[i] = Math.min(ans[i], prev - i);
	}

	return ans;
}