Longest Substring without Duplication – Dynamic Programming Solutions

This is a C++ Program that Solves Longest Substring Without Duplication Problem using Dynamic Programming technique.

Problem Description

You are given a string. Find the length of longest substring of the given string which does not contain any duplicate character.

Problem Solution

Process the string in a linear fashion keeping record of the visited characters and the index of their most recent appearance. If a character is repeated, reset the current substring.

Expected Input and Output

Case-1:

string - AECDEFGDHKGL
length of longest substring without duplicate characters = 6 (EFGDHK)
Program/Source Code

Here is source code of the C++ Program to Solve Longest Substring Without Duplication Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
advertisement
  1. #include<iostream>
  2. #include<string>
  3. #include<utility>
  4. #include<vector>
  5.  
  6. using namespace std;
  7.  
  8. int longestWithoutRepeating(string str)
  9. {
  10.     vector<int> processed(256,-1);
  11.  
  12.     //length of the current substring without any repeating character
  13.     int current=0;
  14.  
  15.     //length of the longest substring without any repeating character
  16.     int longest=0;
  17.  
  18.     for(int i=0;i<str.length();i++)
  19.     {
  20.         //if this character is not yet processed or is not present in current substring
  21.         if(processed[str[i]]==-1 || processed[str[i]]<(i-current) )
  22.         {
  23.             current++;
  24.             processed[str[i]]=i;
  25.  
  26.             if(current>longest)
  27.                 longest=current;
  28.         }
  29.  
  30.         else
  31.         {
  32.             //this character is repeated
  33.             //reset the length of current substring without any repeating character
  34.             current=i-processed[str[i]];
  35.             processed[str[i]]=i;
  36.         }
  37.  
  38.     }
  39.  
  40.     return longest;
  41. }
  42.  
  43. int main()
  44. {
  45.     string str;
  46.  
  47.     cout<<"Enter the string"<<endl;
  48.     getline(cin, str);
  49.  
  50.     cout<<"Longest substring without repeating characters is "<<endl;
  51.     cout<<longestWithoutRepeating(str);
  52.  
  53.     cout<<endl;
  54.     return 0;
  55. }
Program Explanation

In the main function, we ask the user to input the string. We pass this value to the function longestWithoutRepeating as parameter. This function will calculate the expected result and return it. The returned value will be displayed on the standard output.

Runtime Test Cases
 
Case-1:
$ g++ longest_substring_without_repeating.cpp
$ ./a.out
Enter the string
AECDEFGDHKGL
Longest substring without repeating characters is 
6

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.