{"id":2654,"date":"2021-10-13T19:20:00","date_gmt":"2021-10-13T13:50:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2654"},"modified":"2022-03-15T02:10:05","modified_gmt":"2022-03-14T20:40:05","slug":"longest-common-prefix","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-common-prefix\/","title":{"rendered":"Longest Common Prefix (With Solution)"},"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=\"#horizontal-scanning-approach\">Horizontal Scanning Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-horizontal-scanning\">C++ Implementation Horizontal Scanning<\/a><\/li><li><a href=\"#-java-implementation-horizontal-scanning\"><meta charset=\"utf-8\">Java Implementation Horizontal Scanning<\/a><\/li><li><a href=\"#-python-implementation-horizontal-scanning\"><meta charset=\"utf-8\">Python Implementation Horizontal Scanning<\/a><\/li><\/ul><li><a href=\"#vertical-scanning-approach\">Vertical Scanning Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-vertical-scanning\">C++ Implementation of Vertical Scanning<\/a><\/li><li><a href=\"#-java-implementation-of-vertical-scanning\"><meta charset=\"utf-8\">Java Implementation of Vertical Scanning<\/a><\/li><li><a href=\"#-python-implementation-of-vertical-scanning\"><meta charset=\"utf-8\">Python Implementation of Vertical Scanning<\/a><\/li><\/ul><li><a href=\"#divide-and-conquer-approach\">Divide and Conquer Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#-java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/a><\/li><li><a href=\"#-python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#binary-search-approach\">Binary Search Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-binary-search-approach\">C++ Implementation of Binary Search Approach<\/a><\/li><li><a href=\"#-java-implementation-of-binary-search-approach\"><meta charset=\"utf-8\">Java Implementation of Binary Search Approach<\/a><\/li><li><a href=\"#-python-implementation-of-binary-search-approach\"><meta charset=\"utf-8\">Python Implementation of Binary Search Approach<\/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 the array of strings S[], you need to find the longest string S which is the prefix of ALL the strings in the array.<\/p>\n\n\n\n<p><strong>Longest common prefix (LCP)<\/strong> for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2.<\/p>\n\n\n\n<p>For Example: longest common prefix of <strong>&#8220;abcdefgh&#8221;<\/strong> and <strong>&#8220;abcefgh&#8221;<\/strong> is <strong>&#8220;ABC&#8221;<\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"452\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Prefix of abc\"  class=\"wp-image-2739 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 452px) 100vw, 452px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Prefix-of-abc.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Prefix-of-abc.png 452w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Prefix-of-abc-271x300.png 271w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Prefix-of-abc-380x420.png 380w\" ><\/figure><\/div>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> S[] = {\u201cabcdefgh\u201d, \u201cabcefgh\u201d}<br><strong>Output:<\/strong> \u201cabc\u201d<br><strong>Explanation:<\/strong> Explained in the image description above<\/p>\n\n\n\n<p><strong>Input:<\/strong> S[] = {&#8220;abcdefgh&#8221;, &#8220;aefghijk&#8221;, &#8220;abcefgh&#8221;}<br><strong>Output:<\/strong> \u201ca\u201d<\/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=\"horizontal-scanning-approach\">Horizontal Scanning Approach<\/h2>\n\n\n\n<p>The idea is to horizontally scan all the characters of the array of strings one by one and find the <strong>Longest Common Prefix<\/strong> among them. The <strong>LCP <\/strong>can be obtained as follows &#8211;&nbsp;<\/p>\n\n\n\n<p><strong>LCP(S1&#8230;SN) = LCP(LCP(LCP(S1, S2), S3),&#8230;., SN)<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"547\"  height=\"481\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Horizantal Scanning Approach\"  class=\"wp-image-2736 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 547px) 100vw, 547px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Horizantal-Scanning-Approach.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Horizantal-Scanning-Approach.png 547w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Horizantal-Scanning-Approach-300x264.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Horizantal-Scanning-Approach-380x334.png 380w\" ><figcaption>Horizontal Scanning Approach<\/figcaption><\/figure><\/div>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Iterate through the string one by one from <strong>S1 <\/strong>till<strong> SN.<\/strong><\/li><li>For each iteration till <strong>ith index<\/strong>, the <strong>LCP(S1&#8230;Si)<\/strong> can be obtained.<\/li><li>In case, the LCP is an empty string, terminate loop and return the empty string.<\/li><li>Else, continue and after scanning of <strong>N<\/strong> strings, the <strong>LCP(S1&#8230;SN) <\/strong>can be obtained.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-horizontal-scanning\">C++ Implementation Horizontal Scanning<\/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\/d1f16eb3f0e03696cd75 title='Interviewbit Ide snippet\/d1f16eb3f0e03696cd75' 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-horizontal-scanning\"><span id=\"java-implementation-horizontal-scanning\"><meta charset=\"utf-8\">Java Implementation Horizontal Scanning<\/span><\/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\/cf1bf15e1b849803bd9f title='Interviewbit Ide snippet\/cf1bf15e1b849803bd9f' 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-horizontal-scanning\"><span id=\"python-implementation-horizontal-scanning\"><meta charset=\"utf-8\">Python Implementation Horizontal Scanning<\/span><\/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\/b5ddebc060028f85f1c1 title='Interviewbit Ide snippet\/b5ddebc060028f85f1c1' 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 size of the array <strong>S[]<\/strong>.<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=\"vertical-scanning-approach\">Vertical Scanning Approach<\/h2>\n\n\n\n<p>The idea is to scan and compare the characters from <strong>top to bottom of the ith<\/strong> index for each string.<\/p>\n\n\n\n<p>This approach is efficient in cases when the <strong>LCP<\/strong> string is very small. Hence, we do not need to perform <strong>K<\/strong> comparisons.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"452\"  height=\"378\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LCP Vertical Scanning Approach\"  class=\"wp-image-2740 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 452px) 100vw, 452px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Vertical-Scanning-Approach.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Vertical-Scanning-Approach.png 452w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Vertical-Scanning-Approach-300x251.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Vertical-Scanning-Approach-380x318.png 380w\" ><figcaption>Vertical Scanning Approach<\/figcaption><\/figure><\/div>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Iterate through the string one by one from <strong>S1 <\/strong>till<strong> SN.<\/strong><\/li><li>Start comparing the <strong>0th<\/strong> index, <strong>1st<\/strong> index \u2026 <strong>ith<\/strong> index<strong> <\/strong>simultaneously for each string.<\/li><li>In case, any of the <strong>ith<\/strong> index characters doesn\u2019t match, terminate the algorithm and return the <strong>LPS(1,i)<\/strong><\/li><li>Else, continue and after scanning of <strong>N<\/strong> strings, the <strong>LCP(S1&#8230;SN) <\/strong>can be obtained.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-of-vertical-scanning\">C++ Implementation of Vertical Scanning<\/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\/e612b6ab1365c43c16d7 title='Interviewbit Ide snippet\/e612b6ab1365c43c16d7' 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-of-vertical-scanning\"><span id=\"java-implementation-of-vertical-scanning\"><meta charset=\"utf-8\">Java Implementation of Vertical Scanning<\/span><\/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\/cf1cc096e8337cdbabba title='Interviewbit Ide snippet\/cf1cc096e8337cdbabba' 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-of-vertical-scanning\"><span id=\"python-implementation-of-vertical-scanning\"><meta charset=\"utf-8\">Python Implementation of Vertical Scanning<\/span><\/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\/2025eebd38d8c1c13ad5 title='Interviewbit Ide snippet\/2025eebd38d8c1c13ad5' 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(K) where K is the sum of all the characters in all strings.<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=\"divide-and-conquer-approach\">Divide and Conquer Approach<\/h2>\n\n\n\n<p>The approach is to divide the given array of strings into various subproblems and merge them to get the <strong>LCP(S1..SN)<\/strong>.<\/p>\n\n\n\n<p>First, divide the given array into two parts. Then, in turn, divide the left and right array obtained into two parts and recursively keep dividing them, until they cannot be divided further.<\/p>\n\n\n\n<p>Mathematically,<strong>LCP(S1\u2026.SN) = LCP(S1\u2026.Sk) + LCP(Sk+1&#8230;SN), <\/strong>where <strong>LCP(S1..SN)<\/strong> is the <strong>LCP <\/strong>of the array of strings and <strong>1 &lt; k &lt; N.<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"547\"  height=\"531\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LCP Divide and Conquer Approach\"  class=\"wp-image-2737 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 547px) 100vw, 547px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCP-Divide-and-Conquer-Approach.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCP-Divide-and-Conquer-Approach.png 547w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCP-Divide-and-Conquer-Approach-300x291.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCP-Divide-and-Conquer-Approach-380x369.png 380w\" ><figcaption>Divide and Conquer Approach<\/figcaption><\/figure><\/div>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Recursively divide the input array of strings into two parts.<\/li><li>For each division, find the <strong>LCP<\/strong> obtained so far.<\/li><li>Merge the obtained <strong>LCP<\/strong> from both the subarrays and return it.<\/li><li>I.e. <strong>LCP(LCP(S[left&#8230;mid], LCP(S[mid + 1, right])) <\/strong>and return it.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<p><iframe loading=\"lazy\" style=\"max-width: 100%; border: none; height: 375px; width: {width}px;\" title=\"Interviewbit Ide snippet\/bcdd7104d5a97548cc3f\" src=\"https:\/\/www.interviewbit.com\/embed\/snippet\/bcdd7104d5a97548cc3f\" width=\"700\" height=\"375\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n\n\n\n<h3 id=\"-java-implementation\"><span id=\"java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/span><\/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\/2ee3986c90f0f852ff72 title='Interviewbit Ide snippet\/2ee3986c90f0f852ff72' 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\"><span id=\"python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/span><\/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\/8c47f4d5e60fd21aad5b title='Interviewbit Ide snippet\/8c47f4d5e60fd21aad5b' 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(K) where K is the sum of all the characters in all strings.<br><strong>Space Complexity:<\/strong> O(M log N), as there are log N recursive calls and each needs a space of <strong>M<\/strong>.<\/p>\n\n\n\n<h2 id=\"binary-search-approach\">Binary Search Approach<\/h2>\n\n\n\n<p>Another way to approach the problem is to use the concept of Binary Search.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Consider the string with the smallest length. Let the length be <strong>L<\/strong>.<\/li><li>Consider a variable <strong>low = 0<\/strong> and <strong>high =&nbsp; L &#8211; 1<\/strong>.<\/li><li>Perform binary search:<ul><li>Divide the string into two halves, i.e. <strong>low &#8211; mid <\/strong>and <strong>mid + 1 <\/strong>to <strong>high<\/strong>.<\/li><li>Compare the substring upto the <strong>mid<\/strong> of this smallest string to every other character of the remaining strings at that index.<\/li><li>If the substring from <strong>0<\/strong> to <strong>mid &#8211; 1 <\/strong>is common among all the substrings, update <strong>low<\/strong> with <strong>mid + 1<\/strong>, else update <strong>high <\/strong>with <strong>mid &#8211; 1<\/strong><\/li><li>If <strong>low == high<\/strong>, terminate the algorithm and return the substring from <strong>0<\/strong> to <strong>mid.<\/strong><\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-of-binary-search-approach\">C++ Implementation of Binary Search Approach<\/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\/2235d05566325adb8c45 title='Interviewbit Ide snippet\/2235d05566325adb8c45' 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-of-binary-search-approach\"><span id=\"java-implementation-of-binary-search-approach\"><meta charset=\"utf-8\">Java Implementation of Binary Search Approach<\/span><\/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\/07a13d8fafad0d8cfe6c title='Interviewbit Ide snippet\/07a13d8fafad0d8cfe6c' 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-of-binary-search-approach\"><span id=\"python-implementation-of-binary-search-approach\"><meta charset=\"utf-8\">Python Implementation of Binary Search Approach<\/span><\/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\/ed461dcfe6b32bcde84f title='Interviewbit Ide snippet\/ed461dcfe6b32bcde84f' 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(K. logN) where K is the sum of all the characters in all strings.<br><strong>Space Complexity:<\/strong> O(1)<\/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\/longest-common-prefix\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Common Prefix<\/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 best time and space complexity of finding the longest prefix string?<\/strong><br>The best time complexity is O(N) and the space complexity is O(1) using the horizontal and vertical scanning approach.<\/p>\n\n\n\n<p><strong>Is the binary search approach better than the other approaches?<\/strong><br>No, the binary search takes O(K*logN) time complexity. Hence, it is not the most efficient approach.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given the array of strings S[], you need to find the longest string S which is&hellip;\n","protected":false},"author":5,"featured_media":2738,"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":[458,459,453],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2654"}],"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=2654"}],"version-history":[{"count":8,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2654\/revisions"}],"predecessor-version":[{"id":7760,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2654\/revisions\/7760"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2738"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2654"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2654"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}