Shortest Distance to a Character

Easy
256.

Shortest Distance to a Character

Shortest Distance to a Character is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Google and Meta interviews.

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

The distance between indices i and j is abs(i - j).

Example 1

Input
s = "loveleetcode", c = "e"
Output
[3,2,1,0,1,0,0,1,2,2,1,0]

Example 2

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

Example 3

Input
s = "aa", c = "a"
Output
[0,0]

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters.
  • c occurs at least once in s.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Distance to a Character — Problem & Solution

Shortest Distance to a Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Shortest Distance to a Character is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Google and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Two Pointers
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

The distance between indices i and j is abs(i - j).

Example 1

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2

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

Example 3

Input: s = "aa", c = "a"
Output: [0,0]

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters.
  • c occurs at least once in s.

Hints for Shortest Distance to a Character

  1. Hint 1

    Two sweeps beat computing every pairwise distance.

  2. Hint 2

    Left to right, track the most recent occurrence of c and record the distance behind you.

  3. Hint 3

    Right to left, track the next occurrence and keep the smaller of the two distances.

How to solve Shortest Distance to a Character

Two sweeps: left to right records the distance to the most recent c, right to left records the distance to the next c; keep the smaller.

Approach

  1. Sweep forward with prev = -∞; on c set prev = i; write out[i] = i - prev.
  2. Sweep backward with prev = +∞; on c set prev = i; write out[i] = min(out[i], prev - i).

Why it works

The nearest occurrence of c to any index is either the closest one on its left or the closest one on its right, and each sweep computes one of those exactly.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • The sentinel for "none yet" must be far enough away that i - prev exceeds any real distance.

Reference solution

Python

def shortestToChar(s: str, c: str):
    n = len(s)
    out = [0] * n
    prev = -10000
    for i in range(n):
        if s[i] == c:
            prev = i
        out[i] = i - prev
    prev = 10000
    for i in range(n - 1, -1, -1):
        if s[i] == c:
            prev = i
        out[i] = min(out[i], prev - i)
    return out

Java

public static int[] shortestToChar(String s, String c) {
    int n = s.length();
    char target = c.charAt(0);
    int[] out = new int[n];
    int prev = -10000;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == target) prev = i;
        out[i] = i - prev;
    }
    prev = 10000;
    for (int i = n - 1; i >= 0; i--) {
        if (s.charAt(i) == target) prev = i;
        out[i] = Math.min(out[i], prev - i);
    }
    return out;
}

C++

vector<int> shortestToChar(string s, string c) {
    int n = (int) s.size();
    char target = c[0];
    vector<int> out(n, 0);
    int prev = -10000;
    for (int i = 0; i < n; i++) {
        if (s[i] == target) prev = i;
        out[i] = i - prev;
    }
    prev = 10000;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == target) prev = i;
        out[i] = min(out[i], prev - i);
    }
    return out;
}

JavaScript

var shortestToChar = function(s, c) {
    const n = s.length;
    const out = new Array(n).fill(0);
    let prev = -10000;
    for (let i = 0; i < n; i++) {
        if (s[i] === c) prev = i;
        out[i] = i - prev;
    }
    prev = 10000;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === c) prev = i;
        if (prev - i < out[i]) out[i] = prev - i;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings