Shortest Distance to a Character

Easy

Asked by:

6 views

Topics:

ArraysStringsTwo Pointers

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 <= 10⁴
s[i] and c are lowercase English letters.
It is guaranteed that c occurs at least once in s.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for the length of the string `s` and can it be empty?
Is the character `c` guaranteed to be present in the string `s`?
Will the string `s` consist of only lowercase English letters, or might it contain other characters (uppercase, numbers, symbols)?
If the character `c` appears multiple times in the string `s`, should I return the shortest distance to any occurrence of `c`?
What is the expected data type for the character `c`? Is it guaranteed to be a single character or could it be a string?

Brute Force Solution

Approach

We need to find the shortest distance from each letter in a word to a specific target letter. The brute force method involves checking the distance from every letter in the word to every instance of the target letter, one at a time, to find the closest one.

Here's how the algorithm would work step-by-step:

For each letter in the given word, we'll find the distance to the closest target letter.
We start by looking at the first letter in the word. We calculate how far away it is from every single occurrence of the target letter within the word.
We find the smallest of all those distances. This becomes the shortest distance for that first letter.
Then, we repeat this process for the second letter, the third letter, and so on, until we've done it for every single letter in the word.
Finally, we put all the shortest distances we calculated into a list, where the first number is the shortest distance for the first letter, the second number is the shortest distance for the second letter, and so on.

Code Implementation

def shortest_distance_to_character_brute_force(word, target_character):

    shortest_distances = []

    for current_index in range(len(word)): 
        # Find the shortest distance for current character
        minimum_distance = float('inf')

        for target_index in range(len(word)): 
            # Check every target to find the minimum distance
            if word[target_index] == target_character:

                distance = abs(current_index - target_index)
                minimum_distance = min(minimum_distance, distance)

        shortest_distances.append(minimum_distance)

    return shortest_distances

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n characters in the string s. For each character, it calculates the distance to every occurrence of the target character c within s. In the worst-case scenario, it might need to compare the current character's position to all other character positions in the string to find the minimum distance. This nested iteration results in roughly n operations for each of the n characters. Therefore, the time complexity is approximately n * n, which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force solution calculates the shortest distance for each letter individually without persistently storing distances between all pairs of letters. It finds the closest target character by iterating through the word, but the intermediate distances are not saved. The space used is limited to a few variables for temporary calculations and tracking the minimum distance found so far, irrespective of the input word's length (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem asks us to find, for each letter in a word, the shortest distance to a specific target character. We can solve this efficiently by making two passes through the word, one from left to right and one from right to left, keeping track of the most recent location of our target character.

Here's how the algorithm would work step-by-step:

First, go through the word from left to right.
As you go, keep track of the closest target character you've seen so far.
Calculate the distance between each letter and the closest target character you've seen.
Now, go through the word from right to left.
Again, keep track of the closest target character you've seen from this direction.
For each letter, compare the distance to the closest target you found going from left to right with the distance to the closest target going from right to left, and pick the smaller distance.
The result is the shortest distance for each letter to the target character.

Code Implementation

def shortest_distance_to_character(word, target_character):
    length_of_word = len(word)
    shortest_distances = [float('inf')] * length_of_word

    # First pass: left to right.
    closest_target_position = float('-inf')
    for index in range(length_of_word):
        if word[index] == target_character:

            # Reset the closest target when found.
            closest_target_position = index

        if closest_target_position != float('-inf'):
            shortest_distances[index] = index - closest_target_position

    # Second pass: right to left.
    closest_target_position = float('inf')
    for index in range(length_of_word - 1, -1, -1):
        if word[index] == target_character:

            # Reset the closest target when found.
            closest_target_position = index

        if closest_target_position != float('inf'):
            distance = abs(index - closest_target_position)

            # Choose minimum distance from both sides.
            shortest_distances[index] = min(shortest_distances[index], distance)

    return shortest_distances

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs two linear scans of the input string s, where n is the length of s. The first scan goes from left to right to find the distance to the nearest character c to the left. The second scan goes from right to left to find the distance to the nearest character c to the right and then compares it with the distance from the left. Since both scans are independent and iterate through each character of the string once, the total time complexity is O(n + n), which simplifies to O(n).

Space Complexity

O(N) – The provided algorithm implicitly creates an output array to store the shortest distances for each character in the input string. This array has the same length as the input string, which we denote as N. Therefore, the algorithm utilizes auxiliary space proportional to the size of the input string, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string S	Return an empty list immediately, as there are no characters to compute distances for.
Null string S or null character C	Throw an IllegalArgumentException or return null, depending on the language conventions, to indicate invalid input.
String S has length 1	If the single character is equal to C, the distance is 0; otherwise, the distance is 1.
Character C does not exist in string S	Return a list where all distances are equal to the length of the string, or use a large constant representing infinity.
Character C appears at the beginning and/or end of string S	The algorithm should correctly compute distances from these boundary occurrences of C.
String S contains only the character C	Return a list of all zeros, as every character is the target character.
Very long string S, approaching maximum string length supported by the language	Ensure the solution's space complexity is efficient, avoiding excessive memory allocation that could lead to out-of-memory errors; a two-pass approach minimizes storage impact.
Multiple occurrences of character C are clustered together	The algorithm must correctly handle overlapping distance ranges from adjacent occurrences of C.

Empty string S

How to Handle:

Return an empty list immediately, as there are no characters to compute distances for.

Null string S or null character C

How to Handle:

Throw an IllegalArgumentException or return null, depending on the language conventions, to indicate invalid input.

String S has length 1

How to Handle:

If the single character is equal to C, the distance is 0; otherwise, the distance is 1.

Character C does not exist in string S

How to Handle:

Return a list where all distances are equal to the length of the string, or use a large constant representing infinity.

Character C appears at the beginning and/or end of string S

How to Handle:

The algorithm should correctly compute distances from these boundary occurrences of C.

String S contains only the character C

How to Handle:

Return a list of all zeros, as every character is the target character.

Very long string S, approaching maximum string length supported by the language

How to Handle:

Ensure the solution's space complexity is efficient, avoiding excessive memory allocation that could lead to out-of-memory errors; a two-pass approach minimizes storage impact.

Multiple occurrences of character C are clustered together

How to Handle:

The algorithm must correctly handle overlapping distance ranges from adjacent occurrences of C.