# Shortest distance to every other character from given character

Given a string *S* and a character *X* where , for some . The task is to return an array of distances representing the shortest distance from the character *X* to every other character in the string.**Examples:**

Input:S = “geeksforgeeks”, X = ‘e’Output:[1, 0, 0, 1, 2, 3, 3, 2, 1, 0, 0, 1, 2]

for S[0] = ‘g’ nearest ‘e’ is at distance = 1 i.e. S[1] = ‘e’.

similarly, for S[1] = ‘e’, distance = 0.

for S[6] = ‘o’, distance = 3 since we have S[9] = ‘e’, and so on.Input:S = “helloworld”, X = ‘o’Output:[4, 3, 2, 1, 0, 1, 0, 1, 2, 3]Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Approach 1:** For each character at index *i* in *S[]*, let us try to find the distance to the next character *X* going left to right, and from right to left. The answer will be the minimum of these two values.

- When going from left to right, we remember the index of the last character
*X*we’ve seen. Then the answer is*i – prev*. - When going from right to left, the answer is
*prev – i*. - We take the minimum of these two answers to create our final distance array.
- Finally, print the array.

Below is the implementation of above approach:

## C++

`// C++ implementation of above approach ` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return required ` `// array of distances ` `void` `shortestDistance(string S, ` `char` `X)` `{ ` ` ` `// Find distance from occurrences of X ` ` ` `// appearing before current character. ` ` ` `int` `prev = INT_MAX;` ` ` `vector<` `int` `> ans;` ` ` ` ` `for` `(` `int` `i = 0; i < S.length(); i++)` ` ` `{ ` ` ` `if` `(S[i] == X) ` ` ` `prev = i; ` ` ` `if` `(prev == INT_MAX)` ` ` `ans.push_back(INT_MAX);` ` ` `else` ` ` `ans.push_back(i - prev);` ` ` `}` ` ` `// Find distance from occurrences of X ` ` ` `// appearing after current character and ` ` ` `// compare this distance with earlier. ` ` ` `prev = INT_MAX; ` ` ` `for` `(` `int` `i = S.length() - 1; i >= 0; i--)` ` ` `{ ` ` ` `if` `(S[i] == X) ` ` ` `prev = i;` ` ` `if` `(prev != INT_MAX)` ` ` `ans[i] = min(ans[i], prev - i); ` ` ` `}` ` ` `for` `(` `auto` `val: ans)` ` ` `cout << val << ` `' '` `;` `}` `// Driver code ` `int` `main()` `{` ` ` `string S = ` `"helloworld"` `;` ` ` `char` `X = ` `'o'` `;` ` ` `shortestDistance(S, X); ` ` ` `return` `0;` `}` `// This code is contributed by Rituraj Jain` |

## Java

`// Java implementation of above approach ` `import` `java.util.*;` `class` `GFG` `{` `// Function to return required ` `// array of distances ` `static` `void` `shortestDistance(String S, ` `char` `X) ` `{ ` ` ` `// Find distance from occurrences of X ` ` ` `// appearing before current character. ` ` ` `int` `prev = Integer.MAX_VALUE; ` ` ` `Vector<Integer> ans = ` `new` `Vector<>(); ` ` ` ` ` `for` `(` `int` `i = ` `0` `; i < S.length(); i++) ` ` ` `{ ` ` ` `if` `(S.charAt(i) == X) ` ` ` `prev = i; ` ` ` `if` `(prev == Integer.MAX_VALUE)` ` ` `ans.add(Integer.MAX_VALUE);` ` ` `else` ` ` `ans.add(i - prev); ` ` ` `} ` ` ` `// Find distance from occurrences of X ` ` ` `// appearing after current character and ` ` ` `// compare this distance with earlier. ` ` ` `prev = Integer.MAX_VALUE;` ` ` `for` `(` `int` `i = S.length() - ` `1` `; i >= ` `0` `; i--) ` ` ` `{ ` ` ` `if` `(S.charAt(i) == X) ` ` ` `prev = i; ` ` ` `if` `(prev != Integer.MAX_VALUE) ` ` ` `ans.set(i, Math.min(ans.get(i), prev - i)); ` ` ` `} ` ` ` `for` `(Integer val: ans) ` ` ` `System.out.print(val+` `" "` `);` `} ` `// Driver code ` `public` `static` `void` `main(String[] args)` `{` ` ` `String S = ` `"geeksforgeeks"` `; ` ` ` `char` `X = ` `'g'` `; ` ` ` `shortestDistance(S, X);` `}` `}` `// This code is contributed by Rajput-Ji` |

## Python3

`# Python3 implementation of above approach` `# Function to return required ` `# array of distances` `def` `shortestDistance(S, X):` ` ` `# Find distance from occurrences of X` ` ` `# appearing before current character.` ` ` `inf ` `=` `float` `(` `'inf'` `)` ` ` `prev ` `=` `inf` ` ` `ans ` `=` `[]` ` ` `for` `i,j ` `in` `enumerate` `(S):` ` ` `if` `S[i] ` `=` `=` `X:` ` ` `prev ` `=` `i` ` ` `if` `(prev ` `=` `=` `inf) : ` ` ` `ans.append(inf)` ` ` `else` `: ` ` ` `ans.append(i ` `-` `prev)` ` ` `# Find distance from occurrences of X` ` ` `# appearing after current character and` ` ` `# compare this distance with earlier.` ` ` `prev ` `=` `inf` ` ` `for` `i ` `in` `range` `(` `len` `(S) ` `-` `1` `, ` `-` `1` `, ` `-` `1` `):` ` ` `if` `S[i] ` `=` `=` `X:` ` ` `prev ` `=` `i` ` ` `if` `(X !` `=` `inf): ` ` ` `ans[i] ` `=` `min` `(ans[i], prev ` `-` `i)` ` ` `# return array of distance` ` ` `return` `ans` `# Driver code` `S ` `=` `"geeksforgeeks"` `X ` `=` `"g"` `# Function call to print answer` `print` `(shortestDistance(S, X))` |

## C#

`// C# implementation of above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` ` ` `// Function to return required ` ` ` `// array of distances` ` ` `public` `static` `void` `shortestDistance(String S, ` `char` `X){` ` ` ` ` `// Find distance from occurrences of X ` ` ` `// appearing before current character. ` ` ` `int` `prev = ` `int` `.MaxValue;` ` ` `List<` `int` `> ans = ` `new` `List<` `int` `>();` ` ` `for` `(` `int` `i=0; i<S.Length; i++)` ` ` `{` ` ` `if` `(S[i] == X)` ` ` `prev = i;` ` ` `if` `(prev == ` `int` `.MaxValue)` ` ` `ans.Add(` `int` `.MaxValue);` ` ` `else` ` ` `ans.Add(i-prev);` ` ` `}` ` ` ` ` `// Find distance from occurrences of X ` ` ` `// appearing after current character and ` ` ` `// compare this distance with earlier.` ` ` `prev = ` `int` `.MaxValue;` ` ` `for` `(` `int` `i=S.Length-1; i>=0; i--)` ` ` `{` ` ` `if` `(S[i] == X)` ` ` `prev = i;` ` ` `if` `(prev != ` `int` `.MaxValue)` ` ` `ans[i] = Math.Min(ans[i], prev-i);` ` ` `}` ` ` ` ` `foreach` `(` `var` `i ` `in` `ans)` ` ` `Console.Write(i + ` `" "` `);` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `String S = ` `"geeksforgeeks"` `;` ` ` `char` `X = ` `'g'` `;` ` ` `shortestDistance(S, X);` ` ` `}` `}` `// This code is contributed by` `// sanjeev2552` |

**Output**

4 3 2 1 0 1 0 1 2 3

**Approach 2: **Create a list holding the occurrence of the character and then create two pointers pointing two immediate locations in this list, now iterate over the string to find the difference from these two pointers and insert the minimum in the result list. If pointer 2 is nearer to the current character, move the pointers one step ahead.

- Create a list holding positions of the required character in the string and an empty list to hold the result array.
- Create two pointers to the list
*p1=0*and*p2=0*if list length is 1 else*p2=1* - Iterate over the string and compare the values at these pointers
*(v1=p1->value & v2=p2->value)*with the current index*(i)*.- If
*i <= v1,*then push*v1-i*in the result list. - Else if
*i <= v2*- if
*i*is nearer to*v1,*then push*i-v1*in the result list - Else push
*v2-i*in the result list and move pointer one step forward if possible

- if
- Else push
*i-v1*into the result list

- If
- Return result list

Below is the implementation of the above approach:

## C++

`// C++ implementation of above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to return required` `// vector of distances` `vector<` `int` `> shortestToChar(string s, ` `char` `c)` `{` ` ` `// list to hold position of c in s` ` ` `vector<` `int` `> list;` ` ` `// list to hold the result` ` ` `vector<` `int` `> res;` ` ` `// length of string` ` ` `int` `len = s.length();` ` ` `// Iterate over string to create list` ` ` `for` `(` `int` `i = 0; i < len; i++) {` ` ` `if` `(s[i] == c) {` ` ` `list.push_back(i);` ` ` `}` ` ` `}` ` ` `int` `p1, p2, v1, v2;` ` ` `// max value of p2` ` ` `int` `l = list.size() - 1;` ` ` `// Initialize the pointers` ` ` `p1 = 0;` ` ` `p2 = l > 0 ? 1 : 0;` ` ` `// Create result array` ` ` `for` `(` `int` `i = 0; i < len; i++) {` ` ` `// Values at current pointers` ` ` `v1 = list[p1];` ` ` `v2 = list[p2];` ` ` `// Current Index is before than p1` ` ` `if` `(i <= v1) {` ` ` `res.push_back(v1 - i);` ` ` `}` ` ` `// Current Index is between p1 and p2` ` ` `else` `if` `(i <= v2) {` ` ` `// Current Index is nearer to p1` ` ` `if` `(i - v1 < v2 - i) {` ` ` `res.push_back(i - v1);` ` ` `}` ` ` `// Current Index is nearer to p2` ` ` `else` `{` ` ` `res.push_back(v2 - i);` ` ` `// Move pointer 1 step ahead` ` ` `p1 = p2;` ` ` `p2 = p2 < l ? (p2 + 1) : p2;` ` ` `}` ` ` `}` ` ` `// Current index is after p2` ` ` `else` `{` ` ` `res.push_back(i - v2);` ` ` `}` ` ` `}` ` ` `return` `res;` `}` `// Driver code` `int` `main()` `{` ` ` `string s = ` `"geeksforgeeks"` `;` ` ` `char` `c = ` `'e'` `;` ` ` `vector<` `int` `> res = shortestToChar(s, c);` ` ` `for` `(` `auto` `i : res)` ` ` `cout << i << ` `" "` `;` ` ` `return` `0;` `}` `// This code is contributed by Shivam Sharma` |

## C

`// C implementation of above approach` `#include <stdio.h>` `#define MAX_SIZE 100` `// Function to return required` `// vector of distances` `void` `shortestToChar(` `char` `s[], ` `char` `c, ` `int` `* res)` `{` ` ` `// list to hold position of c in s` ` ` `int` `list[MAX_SIZE];` ` ` `// length of string` ` ` `int` `len = 0;` ` ` `// To hold size of list` ` ` `int` `l = 0;` ` ` `// Iterate over string to create list` ` ` `while` `(s[len] != ` `'\0'` `) {` ` ` `if` `(s[len] == c) {` ` ` `list[l] = len;` ` ` `l++;` ` ` `}` ` ` `len++;` ` ` `}` ` ` `int` `p1, p2, v1, v2;` ` ` `// max value of p2` ` ` `l = l - 1;` ` ` `// Initialize the pointers` ` ` `p1 = 0;` ` ` `p2 = l > 0 ? 1 : 0;` ` ` `// Create result array` ` ` `for` `(` `int` `i = 0; i < len; i++) {` ` ` `// Values at current pointers` ` ` `v1 = list[p1];` ` ` `v2 = list[p2];` ` ` `// Current Index is before than p1` ` ` `if` `(i <= v1) {` ` ` `res[i] = (v1 - i);` ` ` `}` ` ` `// Current Index is between p1 and p2` ` ` `else` `if` `(i <= v2) {` ` ` `// Current Index is nearer to p1` ` ` `if` `(i - v1 < v2 - i) {` ` ` `res[i] = (i - v1);` ` ` `}` ` ` `// Current Index is nearer to p2` ` ` `else` `{` ` ` `res[i] = (v2 - i);` ` ` `// Move pointer 1 step ahead` ` ` `p1 = p2;` ` ` `p2 = p2 < l ? (p2 + 1) : p2;` ` ` `}` ` ` `}` ` ` `// Current index is after p2` ` ` `else` `{` ` ` `res[i] = (i - v2);` ` ` `}` ` ` `}` `}` `// Driver code` `int` `main()` `{` ` ` `char` `s[] = ` `"geeksforgeeks"` `;` ` ` `char` `c = ` `'e'` `;` ` ` `int` `res[MAX_SIZE];` ` ` `shortestToChar(s, c, res);` ` ` `int` `i = 0;` ` ` `while` `(s[i] != ` `'\0'` `)` ` ` `printf` `(` `"%d "` `, res[i++]);` ` ` `return` `0;` `}` `// This code is contributed by Shivam Sharma` |

**Output**

1 0 0 1 2 3 3 2 1 0 0 1 2

**Time Complexity:** O(n)

**Space Complexity:** O(n)