algoadvance

Given a string s and a character c, return an array of integers representing the shortest distance from the character c in the string.

Clarifying Questions

1. Q: What should be the output if the character c is not found in the string s? A: The problem guarantees that the character c will be present in the string s.

2. Q: Can the string contain uppercase and lowercase letters? A: Yes, the string can contain uppercase and lowercase letters.

3. Q: Are there any constraints on the length of the string s? A: The length of the string s can range from 1 to 10,000.

Strategy

To solve this problem, we can take the following steps:

1. Pass from Left to Right: Traverse the string from left to right, tracking the position of the last-seen character c. Calculate the distance from each character to this last-seen position and store it in a result array.
2. Pass from Right to Left: Traverse the string from right to left, again tracking the position of the last-seen character c. Update the result array with the minimum distance found from either of the two passes.

Code

def shortestToChar(s: str, c: str) -> [int]:
    n = len(s)
    result = [float('inf')] * n
    
    # Left to right pass
    prev_position = float('-inf')
    for i in range(n):
        if s[i] == c:
            prev_position = i
        result[i] = i - prev_position
    
    # Right to left pass
    prev_position = float('inf')
    for i in range(n-1, -1, -1):
        if s[i] == c:
            prev_position = i
        result[i] = min(result[i], prev_position - i)
    
    return result

# Example Usage
s = "loveleetcode"
c = 'e'
print(shortestToChar(s, c))

Time Complexity

• Time Complexity: The solution requires two passes through the string, each taking linear time. Thus, the overall time complexity is O(n), where n is the length of the string s.
• Space Complexity: We are using an additional array of size n to store the result, so the space complexity is O(n).

This approach ensures we efficiently compute the shortest distance from each character in the string s to the given character c.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?