Shortest Distance to a Character - codepath/compsci_guides GitHub Wiki

• 🔗 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.