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 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;
    }
}