LeetCode 821 - Shortest Distance to a Character

https://leetcode.com/problems/shortest-distance-to-a-character/description/

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:

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

https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/C++JavaPython-Easy-and-Concise-with-Explanation

    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int[] res = new int[n];
        int pos = -n;
        for (int i = 0; i < n; ++i) {
            if (S.charAt(i) == C) pos = i;
            res[i] = i - pos;
        }
        for (int i = n - 1; i >= 0; --i) {
            if (S.charAt(i) == C)  pos = i;
            res[i] = Math.min(res[i], Math.abs(i - pos));
        }
        return res;
    }

We give it one more loop at first to find all character C and initialize distance to 0.

    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) res[i] = S.charAt(i) == C ? 0 : n;
        for (int i = 1; i < n; ++i) res[i] = Math.min(res[i], res[i - 1] + 1);
        for (int i = n - 2; i >= 0; --i) res[i] = Math.min(res[i], res[i + 1] + 1);
        return res;
    }

https://leetcode.com/problems/shortest-distance-to-a-character/discuss/126116/Concise-java-solution-with-detailed-explanation.-Easy-understand!!!

/** "loveleetcode" "e"
 *  1. put 0 at all position equals to e, and max at all other position
 *     we will get [max, max, max, 0, max, 0, 0, max, max, max, max, 0]
 *  2. scan from left to right, if =max, skip, else dist[i+1] = Math.min(dp[i] + 1, dp[i+1]), 
 *     we can get [max, max, max, 0, 1, 0, 0, 1, 2, 3, 4, 0]
 *  3. scan from right to left, use dp[i-1] = Math.min(dp[i] + 1, dp[i-1])
 *     we will get[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0] 
 */
    public int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] dist = new int[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) continue;
            dist[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < n-1; i++) {
            if (dist[i] == Integer.MAX_VALUE) continue;
            else dist[i + 1] = Math.min(dist[i+1], dist[i] + 1);
        }
        for (int i = n-1; i > 0; i--) {
            dist[i-1] = Math.min(dist[i-1], dist[i] + 1);
        }
        return dist; 
    }

https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125850/Java-Single-Pass-with-Trailing-Pointer-(Concise)

Idea is exactly the same as other solutions using stack or two pointers. Keep track of the last seen target character C as well as a left pointer pointing to the last non C character.

If you hit a nonC character and have not seen any C yet, max out that value.

If you hit a nonC character and have seen a C, the current distance to C is the current position i minus the index of the last seen C.

If you hit a C, update all entries from the left pointer up until the current index with the correct value. This is the minimum between the distance to the current C and the previous distance to another C. Finally, update the last seen C index to the current index.

    public int[] shortestToChar(String S, char C) {
        int[] result = new int[S.length()];
        
        int lastC = -1;
        int lastNonC = 0;
        
        for(int i = 0; i<S.length(); i++)
            if(S.charAt(i) == C){
                while(lastNonC<=i)
                    result[lastNonC] = Math.min(result[lastNonC], i-lastNonC++);
                lastC = i;
            }else
                result[i] = lastC != -1 ? i-lastC : Integer.MAX_VALUE;
        
        return result;
    }

package com.lifelongprogrammer.interview;

class Solution {

  public static void main(String[] args) {

  }

  public int[] shortestToChar(String str, char ch) {

    int[] result = new int[str.length()];

    int prevIdx = -1;

    int curIdx = -1;

    for (int i = 0; i < result.length; i++) {

      if (str.charAt(i) == ch) {

        curIdx = i;

        result[i] = 0;

        // handle prevIdx to currIdx

      for (int j = Math.max(0, prevIdx); j < curIdx; j++) {

        if (prevIdx == -1) {

          result[j] = curIdx - j;

        } else {

          result[j] = Math.min(j - prevIdx, curIdx - j);

        }

      }

    }

    //

    prevIdx = curIdx;

  }

  // case xx e (xxxx last part)

  if (curIdx != str.length() - 1) {

    for (int j = Math.max(0, prevIdx); j < str.length(); j++) {

      result[j] = j - prevIdx;

    }

  }

  return result;

}

For each index S[i], let's try to find the distance to the next character C going left, and going right. The answer is the minimum of these two values.

Algorithm

When going left to right, we'll remember the index prev of the last character C we've seen. Then the answer is i - prev.

When going right to left, we'll remember the index prev of the last character C we've seen. Then the answer is prev - i.

We take the minimum of these two answers to create our final answer.

    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = Integer.MIN_VALUE / 2;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = i - prev;
        }

        prev = Integer.MAX_VALUE / 2;
        for (int i = N-1; i >= 0; --i) {
            if (S.charAt(i) == C) prev = i;
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }