Welcome to Subscribe On Youtube

821. Shortest Distance to a Character

Description

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 distance from index i to the closest occurrence of character c in s.

The distance between two indices i and j is abs(i - j), where abs is the absolute value function.

 

Example 1:

 Input: s = "loveleetcode", c = "e" Output: [3,2,1,0,1,0,0,1,2,2,1,0] Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed). The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3. The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2. For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1. The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

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.
  • It is guaranteed that c occurs at least once in s.

Solutions

  • class Solution { public int[] shortestToChar(String s, char c) { int n = s.length(); int[] ans = new int[n]; final int inf = 1 << 30; Arrays.fill(ans, inf); for (int i = 0, pre = -inf; i < n; ++i) { if (s.charAt(i) == c) { pre = i; } ans[i] = Math.min(ans[i], i - pre); } for (int i = n - 1, suf = inf; i >= 0; --i) { if (s.charAt(i) == c) { suf = i; } ans[i] = Math.min(ans[i], suf - i); } return ans; } } 
  • class Solution { public: vector<int> shortestToChar(string s, char c) { int n = s.size(); const int inf = 1 << 30; vector<int> ans(n, inf); for (int i = 0, pre = -inf; i < n; ++i) { if (s[i] == c) { pre = i; } ans[i] = min(ans[i], i - pre); } for (int i = n - 1, suf = inf; ~i; --i) { if (s[i] == c) { suf = i; } ans[i] = min(ans[i], suf - i); } return ans; } }; 
  • class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: n = len(s) ans = [n] * n pre = -inf for i, ch in enumerate(s): if ch == c: pre = i ans[i] = min(ans[i], i - pre) suf = inf for i in range(n - 1, -1, -1): if s[i] == c: suf = i ans[i] = min(ans[i], suf - i) return ans 
  • func shortestToChar(s string, c byte) []int { n := len(s) ans := make([]int, n) const inf int = 1 << 30 pre := -inf for i := range s { if s[i] == c { pre = i } ans[i] = i - pre } suf := inf for i := n - 1; i >= 0; i-- { if s[i] == c { suf = i } ans[i] = min(ans[i], suf-i) } return ans } 
  • function shortestToChar(s: string, c: string): number[] { const n = s.length; const inf = 1 << 30; const ans: number[] = new Array(n).fill(inf); for (let i = 0, pre = -inf; i < n; ++i) { if (s[i] === c) { pre = i; } ans[i] = i - pre; } for (let i = n - 1, suf = inf; i >= 0; --i) { if (s[i] === c) { suf = i; } ans[i] = Math.min(ans[i], suf - i); } return ans; } 
  • impl Solution { pub fn shortest_to_char(s: String, c: char) -> Vec<i32> { let c = c as u8; let s = s.as_bytes(); let n = s.len(); let mut res = vec![i32::MAX; n]; let mut pre = i32::MAX; for i in 0..n { if s[i] == c { pre = i as i32; } res[i] = i32::abs((i as i32) - pre); } pre = i32::MAX; for i in (0..n).rev() { if s[i] == c { pre = i as i32; } res[i] = res[i].min(i32::abs((i as i32) - pre)); } res } }

All Problems

All Solutions