# Longest substring without repeating characters

Given : A string of characters, some of which could be repeating.
Objective : To find the longest substring within the given string that does not contain any repeating characters.
Example : In the given string [ a b b b a c ], the longest substring without repeating characters is [ b a c ].

Idea : To solve this problem a simple sliding window protocol is used where the window holds non-repeating characters.
- The window expands to the right when a non-repeating character is found.
- The window contracts from the left to exclude the repeating character.

Sliding Window

• The sliding window has 2 pointers Start and End to keep track of the longest substring of non-repeating characters.
• The End pointer reads the characters and moves to the right when a non-repeating charcter is found. ( window expands )
• When the End pointer sees a repeating character, the Start pointer moves to the right till it excludes all the characters till the repeating character. ( window contracts ).

Data structures used : A map or a set ( C++ ) could be used to keep a record of the characters in the sliding window. Whenever the End pointer reads a character, this map / set is read to check if the character is found in the map ( repeating ) or not found ( non-repeating ).

Example : Consider the string : [ a b b a ]

Start End Contents of
Map / Set
Max length (ending at End)
( End - Start + 1 )
Max String Operation
[ a b b a ]
0
[ a b b a ]
0
( ) New character a found.
Insert a into the map.
0 - 0 + 1 = 1
[ a ] -Move End pointer.
[ a b b a ]
0
[ a b b a ]
1
( a ) New character b found.
Insert b into the map.
1 - 0 + 1 = 2
[ a b ] -Move End pointer.
[ a b b a ]
0
[ a b b a ]
2
( a b ) Repeated character b found
in the map.
No new max length calculated.
No new max string
calculated.
-Move start pointer beyond the
repeated character b.
-Remove all the characters till
the repeated character b.
- i.e Remove ( a, b ).
-Insert the current character b.
Move End pointer.
[ a b b a ]
2
[ a b b a ]
3
( b ) New character a found.
Insert a into the map.
3 - 2 + 1 = 2
[ b a ] not > [ a b ] -Move End pointer.

Longest max string found : [ a b ]

C++ : Finding the longest substring with non-repeated characters

``````#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<set>

using namespace std;

// Function for finding the longest substring without repeated characters.
void LongestSubstring (string str) {

// map<char,int> table;
// Set performs better than a map, since we don't really use the index position of the
// characters.
set<char> table;

int start = 0, end = 0, max_length = 0;
string result;

while (end < str.size()) {

if (table.find(str[end]) == table.end()) { // New character found. Expand the window.
if (max_length < ( end - start + 1)) {
max_length = end - start + 1;
result = str.substr(start, end - start + 1);
}
} else {
// Repeating character found. Contract the window.
// Move the start pointer till it gets beyond the repeated character,
// also remove the entries of all the charcters found till the repated character.
while (str[start] != str[end]) {
table.erase(str[start]);
start++;
}
table.erase(str[start]); // erase the repeated character.
start++;
}

//table[s[end]] = end;  // for map
table.insert(str[end]); // Store the found characters.
end++; // expand the window by moving the end pointer.
}
cout << "Length : " << max_length << " Substr : " << result << endl;
}

int main () {

vector<string> strings = { "abcabcbb", "abba", "aaaa", "abcdeabcdef", "", "pwwkew", "abbbac" };
for (const auto & str : strings) {
cout << "\nString : " << str << endl;
LongestSubstring(str);
}
return 0;
}
``````

Output

``````String : abcabcbb
Length : 3 Substr : abc

String : abba
Length : 2 Substr : ab

String : aaaa
Length : 1 Substr : a

String : abcdeabcdef
Length : 6 Substr : abcdef

String :
Length : 0 Substr :

String : pwwkew
Length : 3 Substr : wke

String : abbbac
Length : 3 Substr : bac
``````