## Sunday, May 13, 2018

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