Secuencia rotada lexicográficamente más pequeña | conjunto 2

Escriba código para encontrar el mínimo lexicográfico en una array circular, por ejemplo, para la array BCABDADAB, el mínimo lexicográfico es ABBCABDAD
Restricción de entrada: 1 < n < 1000 

Ejemplos: 

Input:  GEEKSQUIZ
Output: EEKSQUIZG

Input:  GFG
Output: FGG

Input :  CAPABCQ
Output : ABCQCAP

Hemos discutido una solución O(n ² Logn) en Rotación lexicográficamente mínima de strings | conjunto 1 . Aquí necesitamos encontrar el índice inicial de rotación mínima y luego imprimir la rotación.

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.

Aquí está el pseudocódigo para el algoritmo. 

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

Aquí está la implementación del algoritmo anterior. 

// C++ program to find lexicographically
// smallest sequence with rotations.
#include <iostream>
using namespace std;
 
// Function to compare lexicographically
// two sequence with different starting
// indexes. It returns true if sequence
// beginning with y is lexicographically
// greater.
bool compareSeq(char S[], int x, int y, int n)
{
    for (int i = 0; i < n; i++) {
        if (S[x] < S[y])
            return false;
        else if (S[x] > S[y])
            return true;
        x = (x + 1) % n;
        y = (y + 1) % n;
    }
    return true;
}
 
// Function to find starting index
// of lexicographically smallest sequence
int smallestSequence(char S[], int n)
{
    int index = 0;
    for (int i = 1; i < n; i++)
 
        // if new sequence is smaller
        if (compareSeq(S, index, i, n))
 
            // change index of current min
            index = i;
 
    return index;
}
 
// Function to print lexicographically
// smallest sequence
void printSmallestSequence(char S[], int n)
{
    int starting_index = smallestSequence(S, n);
    for (int i = 0; i < n; i++)
        cout << S[(starting_index + i) % n];
}
 
// driver code
int main()
{
    char S[] = "DCACBCAA";
    int n = 8;
    printSmallestSequence(S, n);
    return 0;
}

// Java program to find lexicographically
// smallest sequence with rotations.
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class */
class LexoSmallest {
    // Function to compare lexicographically
    // two sequence with different starting
    // indexes. It returns true if sequence
    // beginning with y is lexicographically
    // greater.
    static boolean compareSeq(char[] S, int x, int y, int n)
    {
        for (int i = 0; i < n; i++) {
            if (S[x] < S[y])
                return false;
            else if (S[x] > S[y])
                return true;
            x = (x + 1) % n;
            y = (y + 1) % n;
        }
        return true;
    }
 
    // Function to find starting index
    // of lexicographically smallest sequence
    static int smallestSequence(char[] S, int n)
    {
        int index = 0;
        for (int i = 1; i < n; i++)
 
            // if new sequence is smaller
            if (compareSeq(S, index, i, n))
 
                // change index of current min
                index = i;
 
        return index;
    }
 
    // Function to print lexicographically
    // smallest sequence
    static void printSmallestSequence(String str, int n)
    {
        char[] S = str.toCharArray();
        int starting_index = smallestSequence(S, n);
        for (int i = 0; i < n; i++)
            System.out.print(S[(starting_index + i) % n]);
    }
 
    // driver code
    public static void main(String[] args)
    {
        String S = "DCACBCAA";
        int n = 8;
        printSmallestSequence(S, n);
    }
}
// This code is contributed by Mr Somesh Awasthi

# Python 3 program to find lexicographically
# smallest sequence with rotations.
 
# Function to compare lexicographically
# two sequence with different starting
# indexes. It returns true if sequence
# beginning with y is lexicographically
# greater.
import copy
 
 
def printSmallestSequence(s):
    m = copy.copy(s)
    for i in range(len(s) - 1):
 
        if m > s[i:] + s[:i]:
            m = s[i:] + s[:i]
 
    return m
 
#Driver Code
if __name__ == '__main__':
 
    st = 'DCACBCAA'
    print(printSmallestSequence(st))
 
 
# This code is contributed by Koushik Reddy B

// C# program to find lexicographically
// smallest sequence with rotations.
using System;
 
class LexoSmallest {
     
    // Function to compare lexicographically
    // two sequence with different starting
    // indexes. It returns true if sequence
    // beginning with y is lexicographically
    // greater.
    static bool compareSeq(string S, int x, int y, int n)
    {
        for (int i = 0; i < n; i++) {
            if (S[x] < S[y])
                return false;
            else if (S[x] > S[y])
                return true;
            x = (x + 1) % n;
            y = (y + 1) % n;
        }
        return true;
    }
 
    // Function to find starting index
    // of lexicographically smallest sequence
    static int smallestSequence(string S, int n)
    {
        int index = 0;
        for (int i = 1; i < n; i++)
 
            // if new sequence is smaller
            if (compareSeq(S, index, i, n))
 
                // change index of current min
                index = i;
 
        return index;
    }
 
    // Function to print lexicographically
    // smallest sequence
    static void printSmallestSequence(string str, int n)
    {
        // char[] S=str.toCharArray();
        int starting_index = smallestSequence(str, n);
        for (int i = 0; i < n; i++)
        Console.Write(str[(starting_index + i) % n]);
    }
 
    // driver code
    public static void Main()
    {
        string S = "DCACBCAA";
        int n = 8;
        printSmallestSequence(S, n);
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find lexicographically
// smallest sequence with rotations.
 
// Function to compare lexicographically
// two sequence with different starting
// indexes. It returns true if sequence
// beginning with y is lexicographically
// greater.
function compareSeq($S, $x, $y, $n)
{
    for($i = 0; $i < $n; $i++)
    {
        if ($S[$x] < $S[$y])
            return false;
        else if ($S[$x] > $S[$y])
            return true;
        $x = ($x + 1) % $n;
        $y = ($y + 1) % $n;
    }
    return true;
}
 
// Function to find starting index
// of lexicographically smallest
// sequence
function smallestSequence($S, $n)
{
    $index = 0;
    for ( $i = 1; $i < $n; $i++)
 
        // if new sequence is smaller
        if (compareSeq($S, $index, $i, $n))
 
            // change index of current min
            $index = $i;
 
    return $index;
}
 
// Function to print lexicographically
// smallest sequence
function printSmallestSequence($S, $n)
{
    $starting_index = smallestSequence($S, $n);
    for ($i = 0; $i < $n; $i++)
        echo $S[($starting_index + $i) % $n];
}
 
    // Driver Code
    $S= "DCACBCAA";
    $n = 8;
    printSmallestSequence($S, $n);
 
// This code is contributed by Ajit.
?>

<script>
// Javascript program to find lexicographically
// smallest sequence with rotations.
     
    // Function to compare lexicographically
    // two sequence with different starting
    // indexes. It returns true if sequence
    // beginning with y is lexicographically
    // greater.
    function compareSeq(S,x,y,n)
    {
        for (let i = 0; i < n; i++)
        {
            if (S[x] < S[y])
                return false;
            else if (S[x] > S[y])
                return true;
            x = (x + 1) % n;
            y = (y + 1) % n;
        }
        return true;
    }
     
    // Function to find starting index
    // of lexicographically smallest sequence
    function smallestSequence(S,n)
    {
        let index = 0;
        for (let i = 1; i < n; i++)
   
            // if new sequence is smaller
            if (compareSeq(S, index, i, n))
   
                // change index of current min
                index = i;
   
        return index;
    }
     
    // Function to print lexicographically
    // smallest sequence
    function printSmallestSequence(str,n)
    {
        let S = str.split("");
        let starting_index = smallestSequence(S, n);
        for (let i = 0; i < n; i++)
            document.write(S[(starting_index + i) % n]);
    }
     
    // driver code
    let S = "DCACBCAA";
    let  n = 8;
    printSmallestSequence(S, n);
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

AADCACBC

Complejidad de tiempo: O(n^2) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Pratik Chhajer . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.