{"id":1463,"date":"2024-01-22T13:00:00","date_gmt":"2024-01-22T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1463"},"modified":"2024-01-24T07:27:55","modified_gmt":"2024-01-24T07:27:55","slug":"longest-substring-without-repeating-characters","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/longest-substring-without-repeating-characters\/","title":{"rendered":"Longest Substring Without Repeating Characters Solved"},"content":{"rendered":"\n<p>A substring is a contiguous sequence of characters within a string. In this article, we will discuss approaches to finding the longest substring in a string, with their implementation in C++, Java, and Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Longest Substring Without Repeating Characters Problem<\/strong><\/h2>\n\n\n\n<p><strong>In the Longest Substring without Repeating Character problem, we are given a string of length n and we have to find the length of the longest substring with no repeating characters.<\/strong><\/p>\n\n\n\n<p><strong>For Example:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> Favtutor<\/p>\n\n\n\n<p><strong>Output:<\/strong> 5<\/p>\n\n\n\n<p><strong>Explanation:<\/strong> favtu<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/Z2LxvJDgpPm0NbOOpN99YFkrJU0zrwKm8HAh59YVeM6vXgX62YrbEOuV35PV72QgZ0kf8yM4zhhk1dcwaTypyo_Qt7QVtIL-gWeh4TG3ImjcVumfzHoulyeld8UBbwFlf-yZJJMB4zcqTm3RgMiHoS0\" alt=\"Example\" style=\"width:283px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<p>The substring \u201cfavtu\u201d does not contain any repeating character and is the longest such substring.<\/p>\n\n\n\n<p>Before moving to an optimized approach, let&#8217;s do it with brute force. This method involves employing two loops: one for traversing the string and another nested loop for identifying different substrings. Subsequently, we examine each substring individually, checking each element. If an element is not found, we store it in a HashSet; otherwise, we break from the loop and increment the count.<\/p>\n\n\n\n<p>Here are the Steps to be followed in this Approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will run an outer loop that traverses the string to consider different starting points for substrings and an inner loop will start from the index ongoing in the outer loop and iterates through the string.<\/li>\n\n\n\n<li>We will declare an unordered set to keep track of the characters in the current substring&nbsp;<\/li>\n\n\n\n<li>At every step, we will check If the character at position j is already in the set, which means we found a repeating character. And we will update the max length by comparing it with the current length.<\/li>\n\n\n\n<li>After this, we will break from the inner loop as we have considered all the substrings starting from position i.<\/li>\n\n\n\n<li>After both loops, the function returns the maximum length of the substring without repeating characters.<\/li>\n<\/ul>\n\n\n\n<p>HashSet is also useful to solve the <a href=\"https:\/\/favtutor.com\/articles\/valid-sudoku\/\">Valid Sudoku problem<\/a>.<\/p>\n\n\n\n<p>The Time complexity of this approach is O(N<sup>2<\/sup>), where N is the length of the input string because we are using nested loops. The Space Complexity of this approach is O(N) where N is the size of the Set taken for storing the elements.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimal Approach<\/strong><\/h2>\n\n\n\n<p>To find the longest substring in a string without repeating characters, we will map each character with the latest index of that character and maintain the frequency of each character.<\/p>\n\n\n\n<p>Here are the steps involved in this Approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will declare a vector to store the last index of each character in the ASCII range (256 characters). Initialized with -1.<\/li>\n\n\n\n<li>Now we will declare the two pointers left and right for the <a href=\"https:\/\/favtutor.com\/blogs\/sliding-window-algorithm\">sliding window<\/a>.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/L3hu3vtf1jjbXBCfaObDFvwXbGEZjVK9Mq1l1OML3WQ0LsdOaKJMd0000pqgJFMCK_B_N-8v-UfaxhpMZ1OKBMOLWr7igzed9_ebBsMN6aW6ODJaFQJYfcdbgahA90oxV7ylq4KGuwU2ar0SyVc6qvU\" alt=\"pointers left and right\" style=\"width:426px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Now we will run a while loop till the right pointer is less than the size of the string.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/9q1Mt4NwDxLzQbtcMU9iXbERF4H0uHjVW7hM4xr84PmRPH9qZX207X2fRaNUjO4GZfyalKkSEaJN4Oz5IbciGVItjdPn4C8Mrz9ViVYfZG4oQSpfO-FECm-JJGfmctEXRoODh1b5Ss25KO0T7oHUEhY\" alt=\"While Loop\" style=\"width:736px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>If the current character is already in the substring (i.e., its last index is not -1), we will adjust the left to the last index of that character + 1 position and update the last index of the current character in the vector.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter is-resized\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/r7FgwP33XPujobXdYPxJrnUgeDeJFF0UO1jw6x2eYTLuqK0if2n8zLg9u_-lxseAcXWxGdlAw44IU3Iqv0JPF_kcbXahb4knTqmpj7hfbrHq-Gvtf01kArBZbUHUuqhPkUvY4F4bDIfSPNe6deCH4nk\" alt=\"Update the last index of the current character\" style=\"width:550px;height:auto\"\/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>At the end of each step, we will update the length of the longest substring without repeating characters and move the right pointer to expand the window.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the C++ program to find the longest substring without repeating characters:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nint lengthofLongestSubstring(string s) {\n    vector&lt;int&gt; mpp(256, -1); \/\/ Vector to store the last index of each character in the ASCII range (256 characters)\n\n    int left = 0, right = 0; \/\/ Pointers for the sliding window\n    int n = s.size(); \/\/ Length of the input string\n    int len = 0; \/\/ Length of the longest substring without repeating characters\n\n    while (right &lt; n) {\n        \/\/ If the current character is already in the substring\n        if (mpp[s[right]] != -1)\n            left = max(mpp[s[right]] + 1, left); \/\/ Move the left pointer to the next position after the last occurrence of the character\n\n        mpp[s[right]] = right; \/\/ Update the last index of the current character\n\n        len = max(len, right - left + 1); \/\/ Update the length of the longest substring\n\n        right++; \/\/ Move the right pointer to expand the window\n    }\n\n    return len; \/\/ Return the length of the longest substring without repeating characters\n}\n\nint main() {\n    string str = &quot;favtutor&quot;;\n    \/\/ Call the function and print the result\n    cout &lt;&lt; &quot;The length of the longest substring without repeating characters is &quot; &lt;&lt; lengthofLongestSubstring(str);\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>We can implement it in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def length_of_longest_substring(s):\n    mpp = [-1] * 256  # List to store the last index of each character in the ASCII range (256 characters)\n\n    left = 0\n    right = 0\n    n = len(s)  # Length of the input string\n    max_len = 0  # Length of the longest substring without repeating characters\n\n    while right &lt; n:\n        # If the current character is already in the substring\n        if mpp[ord(s[right])] != -1:\n            left = max(mpp[ord(s[right])] + 1, left)  # Move the left pointer to the next position after the last occurrence of the character\n\n        mpp[ord(s[right])] = right  # Update the last index of the current character\n\n        max_len = max(max_len, right - left + 1)  # Update the length of the longest substring\n\n        right += 1  # Move the right pointer to expand the window\n\n    return max_len  # Return the length of the longest substring without repeating characters\n\n# Example Usage\nstr_value = &quot;favtutor&quot;\nprint(&quot;The length of the longest substring without repeating characters is&quot;, length_of_longest_substring(str_value))<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>The same solution can be implemented in Java also:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class LengthOfLongestSubstring {\n    public static int lengthOfLongestSubstring(String s) {\n        int[] mpp = new int[256];  \/\/ Array to store the last index of each character in the ASCII range (256 characters)\n        Arrays.fill(mpp, -1);\n\n        int left = 0;\n        int right = 0;\n        int n = s.length();  \/\/ Length of the input string\n        int maxLen = 0;  \/\/ Length of the longest substring without repeating characters\n\n        while (right &lt; n) {\n            \/\/ If the current character is already in the substring\n            if (mpp[s.charAt(right)] != -1) {\n                left = Math.max(mpp[s.charAt(right)] + 1, left);  \/\/ Move the left pointer to the next position after the last occurrence of the character\n            }\n\n            mpp[s.charAt(right)] = right;  \/\/ Update the last index of the current character\n\n            maxLen = Math.max(maxLen, right - left + 1);  \/\/ Update the length of the longest substring\n\n            right++;  \/\/ Move the right pointer to expand the window\n        }\n\n        return maxLen;  \/\/ Return the length of the longest substring without repeating characters\n    }\n\n    public static void main(String[] args) {\n        \/\/ Example Usage\n        String strValue = &quot;favtutor&quot;;\n        System.out.println(&quot;The length of the longest substring without repeating characters is &quot; + lengthOfLongestSubstring(strValue));\n    }\n}<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-93182f6675e243f2618afc7bd897882d\" style=\"background-color:#fedcba\"><code>The length of the longest substring without repeating characters is 5<\/code><\/pre>\n\n\n\n<p>The Time Complexity of the algorithm is O(n), where n is the length of the input string because we are iterating through the string using two pointers (left and right) in a single pass. The Space Complexity is constant, O(1), or O(256) in terms of the character set.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we have discussed the longest substring without repeating the character <a href=\"https:\/\/leetcode.com\/problems\/longest-substring-without-repeating-characters\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow sponsored\">leetcode problem<\/a> using the optimal approach by using the concept of sliding window and also implemented their code in C++, Java, and Python. And also discussed their time and space complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Find the solution to the leetcode problem to find the longest substring without repeating characters with implementation in C++, Java and Python.<\/p>\n","protected":false},"author":12,"featured_media":1465,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1463","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1463","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1463"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1463\/revisions"}],"predecessor-version":[{"id":1502,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1463\/revisions\/1502"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1465"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}