You're given a string s and a character c. The task is to find the shortest distance between each character in s and the character c. You need to return an array where each element represents the distance of the corresponding character in s to the nearest occurrence of c.

Example:

Input:

• String s = "loveleetcode"
• Character c = 'e'

Output:

• [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Approach & Intuition:

The idea is to find the closest position of the character c for each character in the string s. Here’s how we can do it:

1. Identify All Positions of c:

   • First, go through the string and collect all the positions where the character c appears.

2. Calculate the Minimum Distance:

   • For each character in s, calculate its distance to every occurrence of c and take the minimum of those distances.

Step-by-Step Breakdown:

1. Store Occurrences:

   • Traverse the string s and note down the positions (indexes) where the character c occurs.

2. Compute Distance for Each Character:

   • For every character in s, calculate its distance from each stored position of c and take the smallest distance.

Code Implementation in C++:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> positionsOfC;  // Store positions of character 'c'
        vector<int> shortestDistances(s.size(), INT_MAX);  // Store the shortest distances

        // Step 1: Collect all positions where 'c' appears
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == c) {
                positionsOfC.push_back(i);
            }
        }

        // Step 2: Calculate shortest distance for each character
        for (int i = 0; i < s.size(); i++) {
            for (int pos : positionsOfC) {
                shortestDistances[i] = min(shortestDistances[i], abs(pos - i));
            }
        }

        return shortestDistances; // Return the final result
    }
};

int main() {
    Solution solution;
    string s = "loveleetcode";
    char c = 'e';
    
    vector<int> result = solution.shortestToChar(s, c);
    
    for (int distance : result) {
        cout << distance << " ";
    }
}

Explanation of C++ Code:

1. Vector positionsOfC:

   • This vector holds all the indices where the character c is found in the string s.

2. Vector shortestDistances:

   • This vector is initialized to the size of the string s, and each element is set to INT_MAX (a large number) to ensure that we can find the minimum distance later.

3. Calculate Shortest Distances:

   • For each character in s, iterate through all the positions of c and calculate the absolute difference. Keep track of the minimum distance for that character.

4. Return Result:

   • After computing the distances, we return the shortestDistances vector.

Java Version:

Here’s the Java version of the solution.

import java.util.*;

class Solution {
    public int[] shortestToChar(String s, char c) {
        List<Integer> positionsOfC = new ArrayList<>(); // To store all positions of 'c'
        int[] shortestDistances = new int[s.length()]; // To store shortest distances

        // Step 1: Collect all positions where 'c' appears
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                positionsOfC.add(i);
            }
        }

        // Step 2: Calculate shortest distance for each character
        for (int i = 0; i < s.length(); i++) {
            int minDistance = Integer.MAX_VALUE;
            for (int pos : positionsOfC) {
                minDistance = Math.min(minDistance, Math.abs(pos - i));
            }
            shortestDistances[i] = minDistance;
        }

        return shortestDistances;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "loveleetcode";
        char c = 'e';

        int[] result = solution.shortestToChar(s, c);

        for (int distance : result) {
            System.out.print(distance + " ");
        }
    }
}

Explanation of the Java Code:

1. List positionsOfC:

   • We use an ArrayList<Integer> to store the positions where the character c is found in the string s.

2. Array shortestDistances:

   • We create an array of integers to store the shortest distances, initialized with the length of the string s.

3. Calculate Minimum Distance:

   • For each character in the string, we calculate the minimum distance to any occurrence of the character c and store it in the shortestDistances array.

4. Return and Print:

   • Finally, we return and print the array of shortest distances.

Optimizations:

This approach works fine but has a time complexity of O(n * m), where n is the length of the string s and m is the number of occurrences of c. We can optimize this by using two sweeps through the string: one from left to right and the other from right to left, which would give a time complexity of O(n).