Longest common substring without repeating characters solution

In intermediate-level interviews, the solution to the ‘Find the longest common substring’ problem is frequently requested. Similarly, the ‘longest substring without repeating characters’ is a common query.

Welcome back, readers. In this blog post, I’ll tackle the longest natural substring’ problem, also found on platforms like LeetCode and GFG, often phrased as locating the longest substring without repeating characters

FREE : If you’re a new visitor preparing for an interview and need help or want to request a new question, you can use the form on the right side to ask your question. It’s free and doesn’t require signing in. Alternatively, you can ask in our Quora space, which is also free, and you’ll receive a response within 24 hours. Go ahead and check it out! do check best way to find duplicates in an array and reverse a linked list recursivel, Master Abstract Factory Design Pattern for Programming Interviews with 5 easy steps

What is substring in programming with example

Let’s grasp the concept of substrings with an example. Take the string ‘interviewspreparation.com’. If we divide it into segments like ‘interviews’, ‘preparation’, ‘com’, or ‘viewpre’, that illustrates understanding of substrings. A substring is a sequential part of a string, not, for instance, ‘compreparation’

Check substring programming example Number of Wonderful Substrings Solution to understand how it is working

How to find the longest substring without repeating characters ?

Let’s delve into the process of constructing logic to determine the longest substring without repeating characters. I’ll be using C# for coding. Feel free to adapt the approach to your preferred programming language.

Firstly, I’ll employ a dictionary to monitor each character in the string. Why a dictionary? Because it facilitates identifying whether the current character is unique or a duplicate.

Now, we handle two variables named ‘maxLength’ and ‘start’. These variables signify our progress: ‘start’ marks the beginning of our substring, and ‘maxLength’ represents the longest substring found so far. Next, we implement logic to ascertain whether the current character is already in the dictionary. If it is, we additionally verify if this character is positioned before or at the same index as our current ‘start’ variable. If true, we update ‘start’ to the length of the current character plus 1.

Lastly, to determine the longest common substring, we include a check. If ‘maxLength’ is greater than the current character index minus ‘start’, we don’t update it. Otherwise, we update ‘maxLength’ to the current character index minus the ‘start’ value.

By following this process, you can successfully identify the longest substring without repeating characters.

Program : longest substring without repeating characters

Allow me to commence the programming section. In this step, I’ll add a program to search for the longest substring within a given string. Hence, I’ll divide the program into three separate steps to implement the longest common substring logic.

Step 1 : Add Require Variables To Start

As the name suggests, I’ll create the necessary variables to proceed with the program and develop a method to return the total characters of the substring. To locate the substring, I’ve created two integer variables named ‘maxLength’ and ‘start’, along with a dictionary named ‘charIndexMap’.

static int lengthOfLongestSubstring(string s)
{
    //code by interviewspreparation.com
    
    int maxLength = 0;
    int start = 0;
    
    Dictionary<char, int> charIndexMap = new Dictionary<char, int>();


    return maxLength;
}

Step 2 : Implement Iteration

In the second step, to locate all substrings, I’ll create a for loop and a temporary char variable named ‘c’, which will be updated with the current character of the given string. Additionally, I’ll update the ‘maxLength’ value to the maximum length between the current ‘maxLength’ and the current iteration index subtracted by our ‘start’ value.

To following that we able to locate total length of given string.

 static int lengthOfLongestSubstring(string s)
 {
    //code by interviewspreparation.com
      
     int maxLength = 0;
     int start = 0;
     Dictionary<char, int> charIndexMap = new Dictionary<char, int>();

     for (int end = 0; end < s.Length; end++)
     {
         char c = s[end]; 

         charIndexMap[c] = end;
         
         maxLength = Math.Max(maxLength, end - start + 1);
     }

     return maxLength;
 }

And I update the value in the ‘charIndexMap’ dictionary with the current iteration index.

Step 3 : Locate Substring of a string

In the last step, as discussed in the logic explanation section of ‘longest common substring’, I’ll add an if condition to determine the current character. If it exists in the ‘charIndexMap’ dictionary and the size of ‘charIndexMap’ is greater than ‘start’, then we’ll update ‘start’ as the current index with plus 1.

static int lengthOfLongestSubstring(string s)
{
    //code by interviewspreparation.com
    
    int maxLength = 0;
    int start = 0;
    Dictionary<char, int> charIndexMap = new Dictionary<char, int>();

    for (int end = 0; end < s.Length; end++)
    {
        char c = s[end]; 

        if (charIndexMap.ContainsKey(c) && charIndexMap[c] >= start)
        {
            start = charIndexMap[c] + 1;
        }

        charIndexMap[c] = end;
        maxLength = Math.Max(maxLength, end - start + 1);
    }

    return maxLength;
}

Following these steps will indeed allow you to find the longest substring without repeating characters in C#! If you encounter any issues or have further questions while implementing the code, feel free to ask for assistance

Summarizing Longest Common Substring Solution

1. Initialization: Define necessary variables such as ‘maxLength’ to track the length of the longest substring found so far, ‘start’ to mark the beginning of the current substring, and ‘charIndexMap’ to keep track of the indices of characters encountered.
   
2. Loop Through String: Iterate through each character of the input string.
   Update ‘maxLength’: Update ‘maxLength’ to the maximum length between the current ‘maxLength’ and the difference between the current index and ‘start’.
   
3. Check for Repeated Characters: Check if the current character exists in the ‘charIndexMap’ dictionary and if its index is greater than or equal to ‘start’.
   
4. Update ‘start’: If the current character is a repeat, update ‘start’ to the index of the repeated character plus 1.
   
5. Update ‘charIndexMap’: Update the index of the current character in the ‘charIndexMap’ dictionary.

Following these steps will enable you to find the longest substring without repeating characters in C#.