Shortest Distance to a Character - Practice Coding Problems

Shortest Distance to a Character - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "loveleetcode", c = "e"

› Output: [3,2,1,0,1,0,0,1,2,2,1,0]

💡 Note: Character 'e' appears at indices 3, 5, 6, and 11. For each position, find distance to nearest 'e'.

Example 2 — Single Character

$ Input: s = "aaab", c = "b"

› Output: [3,2,1,0]

💡 Note: Character 'b' only appears at index 3, so distances are [3,2,1,0].

Example 3 — All Same Character

$ Input: s = "abaa", c = "a"

› Output: [0,1,0,0]

💡 Note: Character 'a' appears at indices 0, 2, and 3. Each position finds nearest 'a'.

Constraints

1 ≤ s.length ≤ 10⁴
s[i] and c are lowercase English letters
It is guaranteed that c occurs in s

Visualization

Tap to expand

Understanding the Visualization

Input

String 'loveleetcode' and target character 'e'

Find Target

Locate all occurrences of 'e' at indices 3, 5, 6, 11

Calculate

For each position, find distance to nearest 'e'

Key Takeaway

🎯 Key Insight: For each position, the closest target character is either the nearest one to the left or to the right

Asked in

f Facebook 25 G Google 20 a Amazon 15

The key insight is that for each position, the closest character can only be to the left or right. The two-pass approach scans left-to-right tracking distances from the left, then right-to-left tracking distances from the right, taking the minimum. Time: O(n), Space: O(1) excluding output.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each position, find distance to nearest character c by checking all positions
Two Pass Scan	O(n)	O(n)	Scan left-to-right then right-to-left to find minimum distances efficiently

Brute Force — Algorithm Steps

For each position i in string
Scan all positions j to find character c
Calculate |i - j| and keep minimum distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Position i=0

Check distances to all 'e' positions: |0-1|=1, |0-3|=3, min=1

Position i=1

Check distances to all 'e' positions: |1-1|=0, |1-3|=2, min=0

Continue

Repeat for all positions to build result array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(char* s, char* c, int* returnSize) {
    int n = strlen(s);
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = n;
    char target = c[0];
    
    for (int i = 0; i < n; i++) {
        int minDist = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (s[j] == target) {
                int dist = abs(i - j);
                if (dist < minDist) {
                    minDist = dist;
                }
            }
        }
        result[i] = minDist;
    }
    
    return result;
}

int main() {
    char s[10001], c[2];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(c, sizeof(c), stdin);
    c[strcspn(c, "\n")] = 0;
    
    int returnSize;
    int* result = solution(s, c, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n iterations, inner loop n iterations each

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler