Shortest Rotated Distance

Given a wordthat contains lower or upper case characters, a starting index that indicates the starting position to begin a search in word, and a target character to find, return the minimum distance between that character at the indexto begin search, to the target character to find under the assumption that wordis a rotated string.

The Idea: First preprocess a distance array, which will provide us with the minimum distance to go from start to a target character within a rotated array. Next preprocess a dictionary that maps all the characters in word, with it's occurrences with the distance array. Note that these have to be sorted in order to later perform binary search. Finally, perform binary search on the list within the dictionary that contains all mappings for a the target character to search for. We know that we found the target word then the current middle element has a smaller distance to the target index, then both its left and right neighbors.

Complexity: O(N + log(N) + N^2log(N)) time. O(N) time for preprocessing the distance array, O(N+N^2Log(N)) for preprocessing the dictionary and sorting all the elements and finally O(logN) time for binary search. O(N) space for the distance array, and another O(N) space for the dictionary mapping, since at worse case, the characters scale linearly with their locations in the distance array.

def sortedCharLocationMap(word, indices):
    """
    :param word: [string] target key mapping
    :param indices: List [int] target value mapping
    :return: dictionary [char]:[List[int]]
    """
    map = collections.defaultdict(list)
    for i, char in enumerate(word):
        map[char].append(indices[i])
    for key, locs in map.items():
        map[key] = sorted(locs)
    return map


def mapRotatedDistances(word, start):
    """
    :param word: [string] rotated word
    :param start: [int] relative to
    :return: List [int]
    """
    distance_ar = [float('inf') for i in range(0, len(word))]
    rev_it = 1

    for i in range(0, len(word)):
        actual = (i + start) % len(word)
        distance_ar[actual] = min(distance_ar[actual], i)
    for i in reversed(range(0, len(word))):
        actual = (i + start) % len(word)
        distance_ar[actual] = min(distance_ar[actual], rev_it)
        rev_it += 1

    return distance_ar


def binarySearchMinDist(dup_chars, left, right, key):
    if (left <= right):
        mid = int(left + abs(left - right) / 2)
        mid_dist = abs(dup_chars[mid] - key)

        if mid + 1 < len(dup_chars) and mid - 1 >= 0:
            if abs(dup_chars[mid+1] - key) >= mid_dist \
                and abs(dup_chars[mid - 1] - key) >= mid_dist:
                return dup_chars[mid]
        elif mid - 1 >= 0 and mid + 1 >= len(dup_chars):
            if abs(dup_chars[mid-1] - key) >= mid_dist:
                return dup_chars[mid]
        elif mid + 1 < len(dup_chars) and mid - 1 < 0:
            if abs(dup_chars[mid+1] - key) >= mid_dist:
                return dup_chars[mid]
        elif mid + 1 >= len(dup_chars) and mid - 1 < 0:
            return dup_chars[mid]

        if dup_chars[mid] > key:
            return binarySearchMinDist(dup_chars, left, mid-1, key)
        else:
            return binarySearchMinDist(dup_chars, mid+1, right, key)
    else:
        return -1


def shortestRotatedDistance(word, start_i, search):
    """
    :param word: [string] full word to search
    :param start_i: [int] index to start search
    :param search: [char] target search
    :return: [int] min distance
    """
    distance_array = mapRotatedDistances(word, start_i)
    char_locs = sortedCharLocationMap(word, distance_array)
    dup_chars = char_locs[search]
    start_i = distance_array[start_i]
    return binarySearchMinDist(dup_chars, 0, len(dup_chars) - 1, start_i)



# find the minimum distance from index i to char c in word
print(shortestRotatedDistance("godding", 0, 'g')) # 0
print(shortestRotatedDistance("godding", 0, 'd')) # 2
print(shortestRotatedDistance("godding", 1, 'n')) # 3
print(shortestRotatedDistance("godding", 5, 'g')) # 1
print("\n")

print(shortestRotatedDistance("dadiedd", 0, 'a')) # 1
print(shortestRotatedDistance("dadiedd", 3, 'd')) # 1
print(shortestRotatedDistance("dadiedd", 2, 'e')) # 2
print("\n")

print(shortestRotatedDistance("ggggggg", 0, 'g')) # 0
print(shortestRotatedDistance("ggggggg", 3, 'g')) # 0
print(shortestRotatedDistance("ggggggg", 2, 'g')) # 0
print("\n")

print(shortestRotatedDistance("ggggggghhhhh", 7, 'g')) # 1
print(shortestRotatedDistance("ggggggghhhhh", 0, 'h')) # 1
print(shortestRotatedDistance("ggggggghhhhh", 1, 'h')) # 2
print("\n")

print(shortestRotatedDistance("ahahahahaha", 0, 'h')) # 1
print(shortestRotatedDistance("ahahahahaha", 1, 'a')) # 1
print(shortestRotatedDistance("ahahahahaha", 5, 'a')) # 1
print("\n")