This is a C++ Program that Solves Longest Substring Without Duplication Problem using Dynamic Programming technique.
You are given a string. Find the length of longest substring of the given string which does not contain any duplicate character.
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.
Case-1:
string - AECDEFGDHKGL length of longest substring without duplicate characters = 6 (EFGDHK)
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.
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int longestWithoutRepeating(string str)
{
vector<int> processed(256,-1);
//length of the current substring without any repeating character
int current=0;
//length of the longest substring without any repeating character
int longest=0;
for(int i=0;i<str.length();i++)
{
//if this character is not yet processed or is not present in current substring
if(processed[str[i]]==-1 || processed[str[i]]<(i-current) )
{
current++;
processed[str[i]]=i;
if(current>longest)
longest=current;
}
else
{
//this character is repeated
//reset the length of current substring without any repeating character
current=i-processed[str[i]];
processed[str[i]]=i;
}
}
return longest;
}
int main()
{
string str;
cout<<"Enter the string"<<endl;
getline(cin, str);
cout<<"Longest substring without repeating characters is "<<endl;
cout<<longestWithoutRepeating(str);
cout<<endl;
return 0;
}
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.
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.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Data Structure Books
- Buy Programming Books
- Practice Programming MCQs
- Apply for Information Technology Internship
- Practice Computer Science MCQs