{"id":27099,"date":"2018-01-05T20:46:58","date_gmt":"2018-01-05T15:16:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27099"},"modified":"2018-01-05T20:46:58","modified_gmt":"2018-01-05T15:16:58","slug":"c-programming-lexicographically-minimum-string-rotation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-lexicographically-minimum-string-rotation\/","title":{"rendered":"C++ Programming – Lexicographically minimum string rotation"},"content":{"rendered":"

Write code to find lexicographic minimum in a circular array, e.g. for the array BCABDADAB, the lexicographic minimum is ABBCABDAD.<\/span><\/p>\n

Source: Google Written Test<\/p>\n

More Examples:<\/p>\n

Input:  GEEKSQUIZ\r\nOutput: EEKSQUIZG\r\n\r\nInput:  GFG\r\nOutput: FGG\r\n\r\nInput:  GEEKSFORGEEKS\r\nOutput: EEKSFORGEEKSG<\/pre>\n
Following is a simple solution. Let the given string be \u2018str\u2019
\n1) Concatenate \u2018str\u2019 with itself and store in a temporary string say \u2018concat\u2019.
\n2) Create an array of strings to store all rotations of \u2018str\u2019. Let the array be \u2018arr\u2019.
\n3) Find all rotations of \u2018str\u2019 by taking substrings of \u2018concat\u2019 at index 0, 1, 2..n-1. Store these rotations in arr[]\n4) Sort arr[] and return arr[0].<\/p>\n[ad type=\u201dbanner\u201d]\n
Following is C++ implementation of above solution.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20simple%20C%2B%2B%20program%20to%20find%20lexicographically%20minimum%20rotation%0A%2F%2F%20of%20a%20given%20string%0A%23include%20%3Ciostream%3E%0A%23include%20%3Calgorithm%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20This%20functionr%20return%20lexicographically%20minimum%0A%2F%2F%20rotation%20of%20str%0Astring%20minLexRotation(string%20str)%0A%7B%0A%20%20%20%20%2F%2F%20Find%20length%20of%20given%20string%0A%20%20%20%20int%20n%20%3D%20str.length()%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20an%20array%20of%20strings%20to%20store%20all%20rotations%0A%20%20%20%20string%20arr%5Bn%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20concatenation%20of%20string%20with%20itself%0A%20%20%20%20string%20concat%20%3D%20str%20%2B%20str%3B%0A%20%0A%20%20%20%20%2F%2F%20One%20by%20one%20store%20all%20rotations%20of%20str%20in%20array.%0A%20%20%20%20%2F%2F%20A%20rotation%20is%20obtained%20by%20getting%20a%20substring%20of%20concat%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20concat.substr(i%2C%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20Sort%20all%20rotations%0A%20%20%20%20sort(arr%2C%20arr%2Bn)%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20the%20first%20rotation%20from%20the%20sorted%20array%0A%20%20%20%20return%20arr%5B0%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20cout%20%3C%3C%20minLexRotation(%22GEEKSFORGEEKS%22)%20%3C%3C%20endl%3B%0A%20%20%20%20cout%20%3C%3C%20minLexRotation(%22GEEKSQUIZ%22)%20%3C%3C%20endl%3B%0A%20%20%20%20cout%20%3C%3C%20minLexRotation(%22BCABDADAB%22)%20%3C%3C%20endl%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
EEKSFORGEEKSG\r\nEEKSQUIZG\r\nABBCABDAD<\/pre>\n
Time complexity of the above solution is O(n2<\/sup>Logn) under the assumption that we have used a O(nLogn) sorting algorithm.<\/p>\n
This problem can be solved using more efficient methods like Booth\u2019s Algorithm<\/a> which solves the problem in O(n) time. We will soon be covering these methods as separate posts.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Write code to find lexicographic minimum in a circular array, e.g. for the array BCABDADAB, the lexicographic minimum is ABBCABDAD.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1],"tags":[80802,73394,73654,75696,75706,80812,73634,80808,80803,75705,73676,70384,73652,80806,80809,80807,72138,71159,73184,73636,73653,80810],"class_list":["post-27099","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","tag-c-words","tag-compare-strings-in-c","tag-competitive-programming-3-pdf","tag-dictionary-order","tag-dictionary-program-in-c","tag-enumeration-grammar","tag-example-of-suffix","tag-good-string","tag-hackerrank-test","tag-ordered-dictionary","tag-permutation","tag-permutation-program-in-c","tag-prefixes-and-suffixes-pdf","tag-programming-dictionary","tag-radix-64","tag-smallest-string","tag-sort-dictionary","tag-sorting-program","tag-string-algorithms","tag-suffix","tag-suffix-of-or","tag-universal-cycles"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27099","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27099"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27099\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}