top of page
Search

# Shortest Distance to a Character

Updated: Mar 25, 2021

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 shortest distance from s[i] to the character c in s.

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]
```

Constraints:

• 1 <= s.length <= 104

• s[i] and c are lowercase English letters.

• c occurs at least once in s.

Solution:

Brute Force:

```class Solution {
public int[] shortestToChar(String s, char c) {
int n=s.length();
int[] result = new int[s.length()];
int cposition = -n;

for(int i=0;i<n;i++)
{
if(s.charAt(i)==c)
{
cposition = i;
}
result[i]=Math.abs(i-cposition);
}
for(int i=n-1;i>=0;i--)
{
if(s.charAt(i)==c)
{
cposition = i;
}
result[i] =Math.min(result[i], Math.abs(i-cposition));
}

return result;
}
}
```

Approach two O(N):

```class Solution {
public int[] shortestToChar(String s, char c) {
int[] result=new int[s.length()];
Arrays.fill(result,Integer.MAX_VALUE);
for(int i=0;i<s.length();i++){
if(s.charAt(i)==c){
for(int j=0;j<s.length();j++){
int temp=Math.abs(j-i);
result[j]=Math.min(temp,result[j]);
}
}
}
return result;
}
}```