Finding length of longest substring without repeating characters

A substring is a consecutive sequence of characters in a string. If the string is “Educative”, the substrings of this string could be “Educ”, “ucati” etc.

Goal

Our goal is to find the length of the longest substring in a string that has all distinct characters.

There are two ways to find the length of the longest substring:

The Simple method extracts all the substrings from a string, and then calculates the length of substrings with only distinct characters. There will be [(n * (n + 1)) / 2] substrings in a string of n characters. This method, however, has very bad time complexity ie. O (n^3).

Another method, however, solves this issue of time complexity and calculates the length in linear time. This method uses some space to keep last index of visited characters. The algorithm starts from the first index and moves towards the end of a string; it keeps track of maximum length of the substring with non-repeating characters visited so far. As the string is traversed, every new character is searched for in the already visited part of the string (a temporary array is used for this). If the character is not present, then the current length is incremented by 1. If the character is already present, then we look for two cases:
- Case 1: The previous occurrence of this character is not the part of current running longest substring. If this is true, then the current length is simply incremented by 1.
- Case 2: If the previous occurrence of this character is part of the current non-repeating character substring, then the current running longest substring changes. Now, it starts from the character which comes right after the previous occurrence of the currently processed character.

#include <bits/stdc++.h> 
using namespace std; 
#define CharacterCount 128 //can change
  
int longestSubseq(char* myString) 
{ 
    int n = strlen(myString); 
    int currentLength = 1; // length of current running substring 
    int maxLength = 1;  
    int previousIndex;  
    int * alreadyVisited = new int[sizeof(int) * CharacterCount]; 
  
    // Initialize the alreadyVisited array as -1, -1 indicates that the character was not visited
    for (int i = 0; i < CharacterCount; i++) 
        alreadyVisited[i] = -1; 
  
    // Mark first character as alreadyVisited
    alreadyVisited[myString[0]] = 0; 
  
    //Start from the second character.
    for (int i = 1; i < n; i++) { 
        previousIndex = alreadyVisited[myString[i]]; 
  
        // -----------Case 1 -----------
        if (previousIndex == -1 || i - currentLength > previousIndex) 
            currentLength++; 
  
        //  ---------- Case 2 -------------
        else { 
            // we check if the length of previous 
            // running substring was more than the current or not
            if (currentLength > maxLength) 
                maxLength = currentLength; 
  
            currentLength = i - previousIndex; 
        } 
        // Index updation of current character 
        alreadyVisited[myString[i]] = i; 
    } 
  
    // Compare the length of last current running longest substring with maxLength and 
    // update maxLength if needed 
    if (currentLength > maxLength) 
        maxLength = currentLength; 
  
    free(alreadyVisited); // free memory 
    return maxLength; 
} 
int main() 
{ 
    char myString[] = "ABABCB"; 
    cout << "My string is : " << myString << endl; 
    int len = longestSubseq(myString); 
    cout << "The length of the longest substring "
         << "with non repeating characters is : "
         << len; 
    
    return 0;
}

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Finding length of longest substring without repeating characters

Goal

Example