Shortest Distance to a Character

🏠 ⬅️ ➡️

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

Example 1:

Input: s = "loveleetcode ", c = "e " Output: [3,2,1,0,1,0,0,1,2,2,1,0] Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

Example 2:

Input: s = "aaab ", c = "b " Output: [3,2,1,0]

Constraints:

  • 1 <= s.length <= 104
  • s[i] and c are lowercase English letters.
  • It is guaranteed that c occurs at least once in s.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, n
    character(len=:), allocatable :: s
    character :: c
    integer, dimension(:), allocatable :: answer

    ! read input
    read(*,*) s
    read(*,*) c

    ! compute answer
    n = len(s)
    allocate(answer(n))
    do i = 1, n
        j = index(s(i:), c)
        if (j /= 0) then
            answer(i) = abs(i - j)
        else
            answer(i) = 0
        end if
    end do

    ! print answer
    write(*,*) answer

end program main
❌ Compiled
❌ Executed
❌ Correct 
module distance_to_closest_occurrence
implicit none
contains

function distance_to_closest_occurrence(s, c) result(answer)
! Returns an array of integers where answer[i] is the distance from index i to the closest occurrence of character c in s
character(len=*), intent(in) :: s
character, intent(in) :: c
integer :: answer(len(s))
integer :: i, j, closest_index

! Initialize answer array with distances from each index to the first occurrence of c in s
do i = 1, len(s)
    if (s(i:i) == c) then
        closest_index = i
        exit
    end if
    answer(i) = i - closest_index
end do

! Update answer array with distances from each index to the closest occurrence of c in s
do i = 1, len(s)
    do j = i + 1, len(s)
        if (s(j:j) == c) then
            closest_index = j
            exit
        end if
    end do
    answer(i) = min(answer(i), j - i)
end do

end function distance_to_closest_occurrence

end module distance_to_closest_occurrence

program test_distance_to_closest_occurrence
use distance_to_closest_occurrence
implicit none

! Examples
print *, distance_to_closest_occurrence("loveleetcode ", "e ") ! [3,2,1,0,1,0,0,1,2,2,1,0]
print *, distance_to_closest_occurrence("aaab ", "b ") ! [3,2,1,0]

end program test_distance_to_closest_occurrence
🌐 Data from online sources 
from typing import List

def hitBricks(grid: List[List[int]], hits: List[List[int]]) -> List[int]:
    def dfs(x, y):
        if not (0 <= x < m) or not (0 <= y < n) or grid[x][y] <= 0:
            return 0
        grid[x][y] = -1
        return 1 + sum(dfs(x + dx, y + dy) for dx, dy in directions)

    m, n = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    for x, y in hits:
        grid[x][y] -= 1

    for j in range(n):
        if grid[0][j] == 1:
            dfs(0, j)

    result = []
    for x, y in hits:
        grid[x][y] += 1
        if grid[x][y] != 1:
            result.append(0)
            continue
        for dx, dy in directions:
            if dfs(x + dx, y + dy) != 0:
                result.append(dfs(x, y) - 1)
                break
        else:
            result.append(0)

    return result

First, we subtract the presence of bricks in the grid according to the hits. Then, we use Depth-First Search (DFS) to determine if a brick can be reached from the top row of the grid.

For every hit position, if there is a brick there, we check if any adjacent bricks are also stable. If any adjacent bricks are stable, we count the total number of bricks that become unstable starting from the hit position by calling the DFS function on its current cell. Finally, we restore the brick in the current hit position and add the number of fallen bricks to the result array.

Note that we subtract and add the presence of bricks in the grid differently in each language. In C++ and Java, we use grid[hit[0]][hit[1]]-- and grid[hit[0]][hit[1]]++. In Python, we use grid[x][y] -= 1 and grid[x][y] += 1. In JavaScript, we use grid[x][y]-- and grid[x][y]++. The rest of the implementation remains the same across all languages.

🌐 Data from online sources 
#include <vector>

std::vector<int> hitBricks(std::vector<std::vector<int>>& grid, std::vector<std::vector<int>>& hits) {
    const int m = grid.size(), n = grid[0].size();
    std::vector<int> result;
    std::vector<std::vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    for (const auto& hit : hits) {
        grid[hit[0]][hit[1]]--;
    }

    function<int(int, int)> dfs = [&](int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) {
            return 0;
        }
        grid[x][y] = -1;
        int sum = 1;
        for (const auto& d : directions) {
            sum += dfs(x + d[0], y + d[1]);
        }
        return sum;
    };

    for (int i = 0; i < n; ++i) {
        if (grid[0][i] == 1) {
            dfs(0, i);
        }
    }

    for (const auto& hit : hits) {
        grid[hit[0]][hit[1]]++;
        if (grid[hit[0]][hit[1]] != 1) {
            result.push_back(0);
            continue;
        }
        for (const auto& d : directions) {
            if (dfs(hit[0] + d[0], hit[1] + d[1])) {
                result.push_back(dfs(hit[0], hit[1]) - 1);
                break;
            }
        }
    }

    return result;
}

First, we subtract the presence of bricks in the grid according to the hits. Then, we use Depth-First Search (DFS) to determine if a brick can be reached from the top row of the grid.

For every hit position, if there is a brick there, we check if any adjacent bricks are also stable. If any adjacent bricks are stable, we count the total number of bricks that become unstable starting from the hit position by calling the DFS function on its current cell. Finally, we restore the brick in the current hit position and add the number of fallen bricks to the result array.

Note that we subtract and add the presence of bricks in the grid differently in each language. In C++ and Java, we use grid[hit[0]][hit[1]]-- and grid[hit[0]][hit[1]]++. In Python, we use grid[x][y] -= 1 and grid[x][y] += 1. In JavaScript, we use grid[x][y]-- and grid[x][y]++. The rest of the implementation remains the same across all languages.