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.
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.
using namespace std;
int longestWithoutRepeating(string str)
//length of the current substring without any repeating character
//length of the longest substring without any repeating character
//if this character is not yet processed or is not present in current substring
if(processed[str[i]]==-1 || processed[str[i]]<(i-current) )
//this character is repeated
//reset the length of current substring without any repeating character
cout<<"Enter the string"<<endl;
cout<<"Longest substring without repeating characters is "<<endl;
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.