Shortest Distance to a Character

Home

Community

Blog Posts

Programming

Tech Topics

Explore

Find Jobs

Shortest Distance to a Character

Asked 9 months ago

1Comments

1 Views

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:

Identify All Positions of c:
- First, go through the string and collect all the positions where the character c appears.
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:

Store Occurrences:
- Traverse the string s and note down the positions (indexes) where the character c occurs.
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:

Vector positionsOfC:
- This vector holds all the indices where the character c is found in the string s.
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.
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.
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:

List positionsOfC:
- We use an ArrayList<Integer> to store the positions where the character c is found in the string s.
Array shortestDistances:
- We create an array of integers to store the shortest distances, initialized with the length of the string s.
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.
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).

Adobe

array

String

easy

1 Responses

Jubair

commented 9 months ago

DRY RUN

s = "loveleetcode"
c = 'e'

Step 1: Find Positions of 'e'

After the first loop, positionsOfC will contain: [3, 5, 6, 11]

Step 2: Calculate Shortest Distances

Now, let's go through each character and calculate its shortest distance to any 'e':

'l' (index 0):
- Distances to 'e': |0-3| = 3, |0-5| = 5, |0-6| = 6, |0-11| = 11
- Shortest = 3
'o' (index 1):
- Distances to 'e': |1-3| = 2, |1-5| = 4, |1-6| = 5, |1-11| = 10
- Shortest = 2
'v' (index 2):
- Distances to 'e': |2-3| = 1, |2-5| = 3, |2-6| = 4, |2-11| = 9
- Shortest = 1
'e' (index 3):
- Distances to 'e': |3-3| = 0, |3-5| = 2, |3-6| = 3, |3-11| = 8
- Shortest = 0
'l' (index 4):
- Distances to 'e': |4-3| = 1, |4-5| = 1, |4-6| = 2, |4-11| = 7
- Shortest = 1
'e' (index 5):
- Distances to 'e': |5-3| = 2, |5-5| = 0, |5-6| = 1, |5-11| = 6
- Shortest = 0
'e' (index 6):
- Distances to 'e': |6-3| = 3, |6-5| = 1, |6-6| = 0, |6-11| = 5
- Shortest = 0
't' (index 7):
- Distances to 'e': |7-3| = 4, |7-5| = 2, |7-6| = 1, |7-11| = 4
- Shortest = 1
'c' (index 8):
- Distances to 'e': |8-3| = 5, |8-5| = 3, |8-6| = 2, |8-11| = 3
- Shortest = 2
'o' (index 9):
- Distances to 'e': |9-3| = 6, |9-5| = 4, |9-6| = 3, |9-11| = 2
- Shortest = 2
'd' (index 10):
- Distances to 'e': |10-3| = 7, |10-5| = 5, |10-6| = 4, |10-11| = 1
- Shortest = 1
'e' (index 11):
- Distances to 'e': |11-3| = 8, |11-5| = 6, |11-6| = 5, |11-11| = 0
- Shortest = 0

Final Result

The final shortestDistances vector will be:

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

Time and Space Complexity

Time Complexity: O(n * m), where n is the length of the string and m is the number of occurrences of the character 'c'.
Space Complexity: O(n), where n is the length of the string (for storing the result).

Optimization Potential

This solution works, but it's not the most efficient. We can optimize it to O(n) time complexity by using two passes through the string: one from left to right and another from right to left. This would eliminate the need for the nested loop.

Shortest Distance to a Character

Example:

Approach & Intuition:

Step-by-Step Breakdown:

Code Implementation in C++:

Explanation of C++ Code:

Java Version:

Explanation of the Java Code:

Optimizations:

Write your comment here !

1 Responses

Step 1: Find Positions of 'e'

Step 2: Calculate Shortest Distances

Final Result

Time and Space Complexity

Optimization Potential