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.

```
#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;
```
```
}
```

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.

Free 30-Day C Certification Bootcamp is Live. Join Now!

« Prev - Maximum Product Cutting using Dynamic Programming

» Next - Stolen Values Problem using Dynamic Programming

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Programming Books
Practice Computer Science MCQs
Check Computer Science Books
Practice Programming MCQs

Recommended Articles: