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(n2Logn) 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.
C++
// 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
// 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
# 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 copydef 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 Codeif __name__ == '__main__': st = 'DCACBCAA' print(printSmallestSequence(st))# This code is contributed by Koushik Reddy B |
C#
// 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// 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// sequencefunction 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 sequencefunction 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.?> |
Javascript
<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> |
Output
AADCACBC
Time Complexity : O(n^2)
Auxiliary Space : O(1)
This article is contributed by Pratik Chhajer. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
