back
Python Code
"""
Approach: Sliding Window
Time Complexity: O(N)
Space Complexity: O(N)
"""
class LongestSubstringWithoutRepeatingCharacters:
def _length_of_longest_substring(self, s: str) -> int:
result = 0
# count of the removed letters from the substring
removed = 0
# set to keep track of letters that do not repeat as we iterate through the string input
visited = set()
# iterate through every character of the input string
for index in range(len(s)):
# check if the character is present in the visited set. Keep removing characters from the left of the input
# string until the current character is not present in the visited set.
while s[index] in visited:
# remove characters from the set starting from 0th index of the string
visited.remove(s[removed])
# increment removed count everytime a character is removed
removed += 1
# add the current character to the visited set
visited.add(s[index])
# result is the max value of all the lengths of the valid substrings
result = max(result, index - removed + 1)
return result
def process(self, input_string: str):
print(f"\nOutput >> {self._length_of_longest_substring(input_string)}\n")
if __name__ == '__main__':
string = input("Enter input string: ")
LongestSubstringWithoutRepeatingCharacters().process(string)
Output
Enter input string: anbkrancbc
Output >> 6
Process finished with exit code 0