{"id":2912,"date":"2021-10-23T10:54:26","date_gmt":"2021-10-23T05:24:26","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2912"},"modified":"2022-03-15T02:27:53","modified_gmt":"2022-03-14T20:57:53","slug":"lexicographically-smallest-string","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/lexicographically-smallest-string\/","title":{"rendered":"Lexicographically Smallest String"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a string <strong>S<\/strong>. The task is to find the lexicographically smallest string possible by inserting a given character.<\/p>\n\n\n\n<p>A string <strong>a<\/strong> is lexicographically smaller than string <strong>b<\/strong> (of the same length) if in the first position where <strong>a<\/strong> and <strong>b<\/strong> differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, &#8220;abc&#8221; is lexicographically smaller than &#8220;bac&#8221; because &#8216;a&#8217; comes before &#8216;b&#8217; in dictionary order.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>S = \u201caxc\u201d, ch = \u2018b\u2019<br><strong>Output: <\/strong>abxc<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>Inserting character <strong>b<\/strong> in the second position gives the lexicographically smallest string.<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;S = \u201cabcd\u201d, ch = \u2018e\u2019<br><strong>Output:<\/strong> abcde<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>Inserting character <strong>e<\/strong> in the last index gives the lexicographically smallest string.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<p>The approach is to insert the given character just before the position, where the <strong>S[i]<\/strong> is lexicographically larger than the character <strong>ch<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"900\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3095 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 900px) 100vw, 900px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-900x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-900x1024.png 900w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-264x300.png 264w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-768x874.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-380x432.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-550x626.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5-800x910.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-5.png 1024w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Iterate over the string from <strong>i = 0<\/strong> till<strong> i = N.<\/strong><\/li><li>If the current character of the string <strong>S[i]<\/strong> is lexicographically larger than the character <strong>ch, <\/strong>insert the character at that index and terminate the loop.<\/li><li>Else, continue iterating and if no such character is found which is lexicographically greater than <strong>ch<\/strong>, insert <strong>ch<\/strong> at the end of the string.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/ca41daf634372f43c38a title='Interviewbit Ide snippet\/ca41daf634372f43c38a' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/fabceb3ff086b6a6adae title='Interviewbit Ide snippet\/fabceb3ff086b6a6adae' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/e657d9264d124a2057ae title='Interviewbit Ide snippet\/e657d9264d124a2057ae' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is the length of the string.<br><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/lexicographically-largest-array\/\" target=\"_blank\" rel=\"noreferrer noopener\">Lexicographically Largest Array<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What is the lexicographically smallest string?<\/strong><br>A string a is lexicographically smaller than string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b<\/p>\n\n\n\n<p><strong>What is the time complexity of the insertion of a character at a given position?<\/strong><br>The time complexity of insertion of a character at a given position is O(1).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string S. The task is to find the lexicographically smallest string possible by inserting&hellip;\n","protected":false},"author":5,"featured_media":3138,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[479],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2912"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2912"}],"version-history":[{"count":7,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2912\/revisions"}],"predecessor-version":[{"id":7764,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2912\/revisions\/7764"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3138"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2912"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2912"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2912"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}