Программа Javascript для поиска лексикографически наименьшей повернутой последовательности | Набор 2

Опубликовано: 2 Сентября, 2022

Напишите код для поиска лексикографического минимума в циклическом массиве, например, для массива BCABDADAB лексикографический минимум равен ABBCABDAD.
Входное ограничение: 1 < n < 1000
Примеры:

Input:  GEEKSQUIZ
Output: EEKSQUIZG

Input:  GFG
Output: FGG

Input :  CAPABCQ
Output : ABCQCAP

 

Мы обсудили решение O(n 2 Logn) в лексикографически минимальном вращении строки | Установите 1. Здесь нам нужно найти начальный индекс минимального вращения, а затем вывести вращение.

1) Initially assume 0 to be current min 
   starting index.
2) Loop through i = 1 to n-1.
   a) For each i compare sequence starting 
      at i with current min starting index
   b) If sequence starting at i is lexicographically 
      smaller, update current min starting 
      index.

Вот псевдокод для алгоритма

function findIndexForSmallestSequence(S, n):
    result = 0
    for i = 1:n-1
        if (sequence beginning at i < 
               sequence beginning at result)
            result = i
        end if
    end for
    return result

Вот реализация вышеуказанного алгоритма.

Выход:

AADCACBC

Временная сложность: O(n^2)
Вспомогательное пространство: O(1)
Пожалуйста, обратитесь к полной статье о лексикографически наименьшей повернутой последовательности | Набор 2 для более подробной информации!