How do you solve Shortest Distance to a Character on LeetCode?

Shortest Distance to a Character (LeetCode #821) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using two passes (left-to-right and right-to-left) allows us to efficiently find the closest character.

What is the time complexity of Shortest Distance to a Character?

The optimal solution for Shortest Distance to a Character runs in O(n) time and uses O(n) space. This complexity is achieved because we only traverse the string twice, making it linear in relation to the length of the string.

What is the brute force solution for Shortest Distance to a Character?

The brute force approach for Shortest Distance to a Character is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each character in the string and calculates the distance to every occurrence of the target character. It's straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Shortest Distance to a Character?

Shortest Distance to a Character uses the following concepts: Array, Two Pointers, String. The recommended patterns to study are: Two Pointers, Sliding Window.

What are the interview tips for Shortest Distance to a Character?

Always think about the time complexity of your solution and how you can optimize it. Explain your thought process clearly while coding; it helps the interviewer understand your approach. Consider edge cases and test your solution with different inputs to ensure correctness.

What are common mistakes when solving Shortest Distance to a Character?

Not considering edge cases where the target character is at the beginning or end of the string. Failing to update the minimum distance correctly when checking from both directions.

#821

Shortest Distance to a Character

Easy

ArrayTwo PointersStringTwo PointersSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a single pass from left to right and then another from right to left, ensuring we find the closest 'c' efficiently. This reduces unnecessary checks and improves performance.

⚙️

Algorithm

5 steps

1Step 1: Initialize an array 'answer' with the same length as 's'.
2Step 2: Loop from left to right, keeping track of the last seen index of 'c'.
3Step 3: For each index, calculate the distance from the last seen index of 'c'.
4Step 4: Loop from right to left, updating the answer with the minimum distance found.
5Step 5: Return 'answer'.

solution.py13 lines

1def shortestToChar(s, c):
2    answer = [0] * len(s)
3    last_position = float('-inf')
4    for i in range(len(s)):
5        if s[i] == c:
6            last_position = i
7        answer[i] = i - last_position
8    last_position = float('inf')
9    for i in range(len(s) - 1, -1, -1):
10        if s[i] == c:
11            last_position = i
12        answer[i] = min(answer[i], last_position - i)
13    return answer

ℹ

Complexity note: This complexity is achieved because we only traverse the string twice, making it linear in relation to the length of the string.

1Using two passes (left-to-right and right-to-left) allows us to efficiently find the closest character.
2Tracking the last seen index of the target character helps in minimizing distance calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.