Blogs Hub

by AskGif | Oct 18, 2020 | Category :coding | Tags : algorithm array data-structure easy leetcode

Shortest Distance to a Character - Array - Easy - LeetCode

Shortest Distance to a Character - Array - Easy - LeetCode

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
 

Note:

S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.

public class Solution {
    public int[] ShortestToChar(string S, char C) {
        var left = new int[S.Length];
        var right = new int[S.Length];
        int j=int.MaxValue;
        bool found = false;
        for(int i=0;i<S.Length;i++){
            if(S[i]==C){
                j=0;
                found=true;
            }
            else if(found){                
                j++;
            }
            left[i]=j;
        }
        
        j = int.MaxValue;
        found = false;
        for(int i=S.Length-1;i>=0;i--){
            if(S[i]==C){
                j=0;
                found = true;
            }
            else if(found){
                j++;
            }
            right[i]=Math.Min(left[i],j);
        }
        
        var res = new int[S.Length];
        for(int i=0;i<S.Length;i++){
            res[i]=Math.Min(left[i],right[i]);
        }
        
        return res;
    }
}

Time Complexity: O(n)

Space Complexity: O(n)