{"id":2920,"date":"2021-10-23T18:10:00","date_gmt":"2021-10-23T12:40:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2920"},"modified":"2022-03-29T17:58:23","modified_gmt":"2022-03-29T12:28:23","slug":"longest-substring-without-repeating-characters","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-substring-without-repeating-characters\/","title":{"rendered":"Longest Substring Without Repeating Characters"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" 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=\"#bruteforce-approach\">Bruteforce Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementations-of-bruteforce-approach\">C++ Implementations of Bruteforce Approach<\/a><\/li><li><a href=\"#java-implementations-of-bruteforce-approach\">Java Implementations of Bruteforce Approach<\/a><\/li><li><a href=\"#python-implementations-of-bruteforce-approach\">Python Implementations of Bruteforce Approach<\/a><\/li><\/ul><li><a href=\"#sliding-window-approach\">Sliding WIndow Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-sliding-window-method\">C++ Code Sliding Window Method<\/a><\/li><li><a href=\"#java-code-sliding-window-method\">Java Code Sliding Window Method<\/a><\/li><li><a href=\"#python-code-sliding-window-method\">Python Code Sliding Window Method<\/a><\/li><\/ul><li><a href=\"#optimised-sliding-window\">Optimised Sliding Window<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-optimised-sliding-window\">C++ Code For Optimised Sliding Window<\/a><\/li><li><a href=\"#java-code-for-optimised-sliding-window\">Java Code For Optimised Sliding Window<\/a><\/li><li><a href=\"#python-code-for-optimised-sliding-window\">Python Code For Optimised Sliding Window<\/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<iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/FqUUxq6ZCx8\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\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 length of the longest substring without repeating characters.<\/p>\n\n\n\n<p>A substring is a <strong>contiguous<\/strong> sequence of characters within a string. For example &#8211; \u201c<strong>view<\/strong>\u201d is a substring of the string \u201c<strong>Interviewbit<\/strong>\u201d.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>S = \u201cabcabcbb\u201d<br><strong>Output: <\/strong>3<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>\u201cabc\u201d is the longest substring without repeating characters among all the substrings.<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;S = \u201cpwwkew\u201d<br><strong>Output:<\/strong> 3<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>\u201cwke\u201d is the longest substring without repeating characters among all the substrings.<\/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=\"bruteforce-approach\">Bruteforce Approach<\/h2>\n\n\n\n<p>The simplest approach to solve this problem is to generate all the substrings of the given string and among all substrings having all unique characters, return the maximum length.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>To generate all substrings of a string, loop from the <strong>start<\/strong> till the <strong>end <\/strong>index of the string. Let us consider, the <strong>start<\/strong> index is <strong>i<\/strong> and the <strong>end <\/strong>index is <strong>j<\/strong>. Run a nested loop from <strong>i = 0<\/strong> to <strong>N &#8211; 1 <\/strong>and <strong>j<\/strong> <strong>=&nbsp; i + 1 <\/strong>till <strong>N<\/strong>. Hence, the substrings can be generated.<\/li><li>To check if the substring contains all unique characters, put all the characters in the set one by one. If any of the characters are already present in the set, skip that string, else consider its length and maximize it.<\/li><\/ul>\n\n\n\n<h3 id=\"c-implementations-of-bruteforce-approach\">C++ Implementations of Bruteforce 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\/1016e592ae61fcb23e0c title='Interviewbit Ide snippet\/1016e592ae61fcb23e0c' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"java-implementations-of-bruteforce-approach\">Java Implementations of Bruteforce 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\/d89b8839181f43e6e310 title='Interviewbit Ide snippet\/d89b8839181f43e6e310' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-implementations-of-bruteforce-approach\">Python Implementations of Bruteforce 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\/caeadd8e7c5430390e47 title='Interviewbit Ide snippet\/caeadd8e7c5430390e47' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin 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^3), where N is the length of the string.<br><strong>Space Complexity:<\/strong> O(min(N, M)), as HashSet is used. N is the length of the string and M is the size of the substrings.<\/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=\"sliding-window-approach\">Sliding WIndow Approach<\/h2>\n\n\n\n<p>In the previous naive approach, we need to repeatedly consider a substring and check if it contains a duplicate character. But due to this, we are performing some repeatable tasks which can be further improved, i.e., if a substring <strong>S[i][j]<\/strong> from index <strong>i<\/strong> to <strong>j &#8211; 1<\/strong> has already been checked to have no duplicate characters, then simply check if <strong>S[j]<\/strong> is a substring of <strong>S[i][j]<\/strong>.<\/p>\n\n\n\n<p>To check if a substring is present in another string can be done in O(N^2).<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"857\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3100 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 857px) 100vw, 857px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-857x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-857x1024.png 857w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-251x300.png 251w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-768x918.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-1286x1536.png 1286w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-380x454.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-550x657.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-800x956.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6-1160x1386.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-6.png 1484w\" ><\/figure>\n\n\n\n<p><strong>Image Source &#8211; <\/strong>Google Images<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Run a loop from <strong>i = 0<\/strong> till <strong>N<\/strong> <strong>&#8211; 1 <\/strong>and consider a <strong>visited array<\/strong>.<\/li><li>Run a nested loop from <strong>j = i + 1<\/strong> to <strong>N &#8211; 1<\/strong> and check whether the current character <strong>S[j]<\/strong> has already been visited.<\/li><li>If <strong>true<\/strong>, break from the loop and consider the next window.<\/li><li>Else, mark the current character as <strong>visited <\/strong>and <strong>maximize<\/strong> the length as <strong>j &#8211; i + 1<\/strong>.<\/li><li>Remove the first character of the previous window and continue.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-sliding-window-method\">C++ Code Sliding Window Method<\/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\/abdfddc34e95c3002aec title='Interviewbit Ide snippet\/abdfddc34e95c3002aec' 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-code-sliding-window-method\">Java Code Sliding Window Method<\/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\/8bbeff492cdd80c82263 title='Interviewbit Ide snippet\/8bbeff492cdd80c82263' 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-code-sliding-window-method\">Python Code Sliding Window Method<\/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\/cdc2c9901bda5525e51c title='Interviewbit Ide snippet\/cdc2c9901bda5525e51c' 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^2), where N is the length of the string.<br><strong>Space Complexity:<\/strong> O(min(N,M)), as a visiting array is used. N is the length of the string and M is the size of the substrings.<\/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=\"optimised-sliding-window\">Optimised Sliding Window<\/h2>\n\n\n\n<p>In the above approach, checking if the substring contains another string, takes O(N^2) time. But can it be improved?<\/p>\n\n\n\n<p>Yes, using a HashSet as a sliding window, we can check if a character has already been visited and is present in the current window. It can be done in O(1).<\/p>\n\n\n\n<p>The approach is to scan the string from left to right using two pointers <strong>left<\/strong> and <strong>right<\/strong>. It helps to keep a track of the maximum <strong>non-repeating substring <\/strong>in the string.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"844\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3101 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-1024x844.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-1024x844.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-300x247.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-768x633.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-380x313.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-550x453.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-800x660.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7-1160x956.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-7.png 1413w\" ><\/figure>\n\n\n\n<p><br><br><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise <strong>left = 0<\/strong> and <strong>right = 0<\/strong>.<\/li><li>Initialise a HashSet to store the characters of the current window.<\/li><li>Slide the index <strong>right <\/strong>&nbsp;toward <strong>N<\/strong> and if it is not present in the current HashSet, slide it further.<\/li><li>Till this point, we have the maximum <strong>non repeating <\/strong>substring length.<\/li><li>If a character is&nbsp; found, which is present in the current window, remove the character from the current window and slide further.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-for-optimised-sliding-window\">C++ Code For Optimised Sliding Window<\/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\/483a81e8167e29f151e7 title='Interviewbit Ide snippet\/483a81e8167e29f151e7' 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-code-for-optimised-sliding-window\">Java Code For Optimised Sliding Window<\/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\/51efd9e42d2e23cb2ab4 title='Interviewbit Ide snippet\/51efd9e42d2e23cb2ab4' 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-code-for-optimised-sliding-window\">Python Code For Optimised Sliding Window<\/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\/b59867e66d53a78bccdf title='Interviewbit Ide snippet\/b59867e66d53a78bccdf' 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(min(N,M)), as HashSet is used. N is the length of the string and M is the size of the substrings.<\/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-substring-without-repeat\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Substring Without Repeat<\/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>How to count occurrences of each character of a string?<\/strong><br>The occurrence of each character can be found by considering a frequency array.<\/p>\n\n\n\n<p><strong>What is the approach used to find the length of the longest non-repeating substring?<\/strong><br>Sliding Window is the most efficient approach to solve this problem.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string S. The task is to find the length of the longest substring without&hellip;\n","protected":false},"author":5,"featured_media":3144,"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":[481],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2920"}],"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=2920"}],"version-history":[{"count":11,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2920\/revisions"}],"predecessor-version":[{"id":7943,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2920\/revisions\/7943"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3144"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2920"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}