• 🔗 Leetcode Link: Shortest Distance to a Character
• 💡 Problem Difficulty: Easy
• ⏰ Time to complete: 15 mins
• 🛠️ Topics: Recursion
• 🗒️ Similar Questions: Valid Palindrome, Valid Palindrome IV, Check Distances Between Same Letters

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

Be sure that you clarify the input and output parameters of the problem:

• How do we verify the distance away from a character?
  • We can check array for distance away from a character.
• What happens if a sting is of length 0?
  • All strings will be 1 character or longer
• What happens if c is not found in s?
  • c is guaranteed to occur at least once in s
• What are the time and space constraints?
  • Time should be O(N) and space should be O(N), N being the length of the string.

Run through a set of example cases:

HAPPY CASE 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. Input: s = "aaab", c = "b" Output: [3,2,1,0] EDGE CASE Input: s = "b", c = "b" Output: [0]

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

• Sort
  • Not helpful, we need to maintain the relative order of the string
• Two pointer solutions (left and right pointer variables)
  • This is a viable technique. We move from the point where c occurs in s, in both directions.
• Storing the elements of the array in a HashMap or a Set
  • Not helpful, how does the hashmap help us find the distance between characters
• Traversing the array with a sliding window
  • We will have aspects of this technique in our solution to break our loop/recursion

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We check the entire string for c. Upon finding c we will seek both ways and update distance away from c as long as the previous distance away from c was smaller.

1. Write a recursive function to handle two pointer solution while updating the distance. a. Set the basecase: Out of bound or previous distance away from c was smaller. b. Set the distance for index and recursively call left and right of index. 2. Call the recursive function at each point where we find c in string. 3. Return the result.

⚠️ Common Mistakes

• Using iterative approach will work here, however will make the code a bit messier and makes the logic harder to express.

Implement the code to solve the algorithm.

class Solution: def shortestToChar(self, s: str, c: str) -> List[int]: # Write a recursive function to handle two pointer solution while updating the distance. def helper(i, distance): # Set the basecase: Out of bound or previous distance away from c was smaller. if i < 0 or i > len(s) - 1 or res[i] <= distance: return # Set the distance for index and recursively call left and right of index. res[i] = distance helper(i + 1, distance + 1) helper(i - 1, distance + 1) # Call the recursive function at each point where we find c in string res = [len(s) for i in range(len(s))] for i, char in enumerate(s): if char == c: helper(i, 0) # Return the result return res

class Solution { public int[] shortestToChar(String S, char C) { int len = S.length(); int[] dist = new int[len]; Arrays.fill(dist, len); // Call the recursive function at each point where we find c in string for(int i = 0; i < len; i++) { if(S.charAt(i) == C) { minimizeSurroundings(S, dist, i, 0); } } // Return the result return dist; } // Write a recursive function to handle two pointer solution while updating the distance private void minimizeSurroundings(String S, int[] dist, int idx, int cur) { // Set the basecase: Out of bound or previous distance away from c was smaller if(idx < 0 || idx >= S.length() || dist[idx] <= cur) return; // Set the distance for index and recursively call left and right of index dist[idx] = cur; minimizeSurroundings(S, dist, idx-1, cur+1); minimizeSurroundings(S, dist, idx+1, cur+1); } }

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the s

• Time Complexity: O(N) because we will run the algorithm at most twice because recursive call will at most read the entire array once, due to early exit when smaller distance away from c is found.
• Space Complexity: O(N) because we need to store results the length of s. Also recursive call maybe the length of the entire string s.