Find the Nearest Target Character and Support Streaming Updates

Problem Description

Design a data structure that maintains a dynamic string of lowercase English letters and supports efficient updates and nearest-character queries.

Implement the NearestCharTracker class:

• NearestCharTracker(s: str): Initializes the object with an initial string s.
• void append(ch: str): Appends a single character ch to the end of the current string.
• void update(index: int, ch: str): Updates the character at index to ch.
• int find_nearest(index: int, target: str): Returns the minimum absolute distance |index - j| such that the character at index j is equal to target. If target does not appear anywhere in the string, return -1.

Example

tracker = NearestCharTracker("aabac")

# String is currently "aabac" (indices 0 to 4)
tracker.find_nearest(2, "a")  # Returns 1 (closest 'a' is at index 1 or 3, distance |2 - 1| = 1)
tracker.find_nearest(2, "c")  # Returns 2 (closest 'c' is at index 4, distance |2 - 4| = 2)
tracker.find_nearest(0, "z")  # Returns -1 ('z' does not exist in the string)

tracker.append("z")
# String is now "aabacz" (index 5 is 'z')
tracker.find_nearest(0, "z")  # Returns 5 (distance |0 - 5| = 5)

tracker.update(1, "z")
# String is now "azbacz" (index 1 is updated from 'a' to 'z')
tracker.find_nearest(0, "z")  # Returns 1 (closest 'z' is at index 1, distance |0 - 1| = 1)

Constraints

• 1 <= len(s) <= 10^5 initially.
• ch and target are lowercase English letters ('a' - 'z').
• 0 <= index < current_length for all calls to update and find_nearest.
• At most 10^5 total calls will be made to append, update, and find_nearest combined.

Edge Cases to Consider

• The target character occurs directly at index (distance should be 0).
• The target character does not exist in the string at all (should return -1).
• The character updated at index is identical to its existing value (no-op update).
• Multiple occurrences of target are equidistant from index on the left and right.