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;
    }
}
16 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.