This problem deals with finding the longest substring length without repeating characters and the characters allowed are of ASCII code characters with 8 bits => 2^8 => 256 characters.
Example :
abcdabcdef
Longest substring without repeating characters is abcdef of length 6.
O(256n) solution can be found @ Longest Substring Without Repeating Characters – LeetCode
1. Outer loop starts with index 0 and inner loop also starts with index 0.
2. We initiate currentStr to empty outside of the loops.
3. Inside the inner loop if the new character is not found we add it to the currentStr.
4. If a repeating character is found we measure the length of substring and store it if it’s maximum and break out of inner loop.
5. In outer loop we check if the end of string is reached by inner loop and update the max length of substring accordingly.
6. If the inner loop was broken due to repeating character, We jump the outer loop index to avoid that repeating character and update the currentStr to suffix beyond the found Index of repeating character.
This algorithm should execute with O(256N) time complexity.
-Vamshi
Leave a Reply