Algotree > Algorithms > Hash Table & Set > Longest substring without repeating characters

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 ]

Finding the longest substring with non-repeated characters

# Function for finding the longest substring without repeating characters.
def LongestSubstring (string : str) :

    table = {}

    start, end, max_length, result = 0, 0, 0, ""

    while (end < len(string)) :

        if string[end] not in table : # New character found. Expand the window.
            if (max_length < ( end - start + 1)) :
                max_length = end - start + 1
                result = string [start : end + 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 ( string[start] != string[end] ) :
                table.pop(string[start], None)
                start += 1
            table.pop(string[start], None) # erase the repeated character.
            start += 1

        table[string[end]] = end # Store the found characters.
        end += 1                 # expand the window by moving the end pointer.

    print ("Length : " + str(max_length) + " Substr : " + result)

def main () :

    strings = [ "abcabcbb", "brazebra", "dickdicky", "smallcatcattysmall", "", "picochu", "oscarslap" ]
    for string in strings :
         print ("\nString : " + string)
         LongestSubstring (string)

if __name__ == "__main__" :
    main()

Output

String : abcabcbb
Length : 3 Substr : abc

String : brazebra
Length : 5 Substr : braze

String : dickdicky
Length : 5 Substr : dicky

String : smallcatcattysmall
Length : 6 Substr : tysmal

String : 
Length : 0 Substr : 

String : picochu
Length : 4 Substr : pico

String : oscarslap
Length : 5 Substr : oscar

#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

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"The most disastrous thing that you can ever learn is your first programming language. - Alan Kay"