Php Program to Find Lexicographically smallest rotated sequence | Set 2

0 0 2 minutes read

Write code to find lexicographic minimum in a circular array, e.g. for the array BCABDADAB, the lexicographic minimum is ABBCABDAD
Input Constraint: 1 < n < 1000
Examples:

Input:  GEEKSQUIZ
Output: EEKSQUIZG

Input:  GFG
Output: FGG

Input :  CAPABCQ
Output : ABCQCAP

We have discussed a O(n²Logn) solution in Lexicographically minimum string rotation | Set 1. Here we need to find the starting index of minimum rotation and then print the rotation.

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.

Here is pseudo-code for algorithm

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

Here is implementation of above algorithm.

PHP

<?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. 
?> 

Output:

AADCACBC

Time Complexity : O(n^2)
Auxiliary Space : O(1)
Please refer complete article on Lexicographically smallest rotated sequence | Set 2 for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!