Algorithms – Length Of The Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters

Example

Input: s = “afcabcbb”

Output: 3

Explanation: The answer is “afc”, with the length of 3.

Discussion

We are going to use “Sliding Window” algorithm.  It is used to solve problems that involve finding a subarray or substring that meets certain criteria within a larger array or string.

Here’s a step-by-step breakdown of how the algorithm works.

1. Initialize variables n (representing the length of the input string s) and longestSubstring to 0.
2. Create an integer array index of size 128. It will be used to store the last index of each character encountered in the string s. The size 128 is chosen because it represents the total number of ASCII characters.
3. Enter a for loop that iterates over each character in the string s.
4. Inside the loop, update the i pointer to the maximum value between its current value and the index of the character at position j in the index array. This ensures that i always points to the start of the current substring without repeating characters.
5. Calculate the length of the current substring (j - i + 1) and compare it with the current value of longestSubstring. If the current substring is longer, update longestSubstring to the length of the current substring.
6. Update the index of the character at position j in the index array to j + 1. This marks the most recent occurrence of the character.
7. After the loop finishes, return the value stored in longestSubstring, which represents the length of the longest substring without repeating characters in the input string s.

The time complexity of this algorithm is O(n), where n is the length of the input string s. This is because the for loop iterates over each character once, and all other operations inside the loop take constant time.

The space complexity is O(1) because the index array has a fixed size of 128, regardless of the size of the input string s. Therefore, the space usage remains constant.

Solution

Java

Python

C++

We have an article on Reversing Integer, click here to find the solution.

Our facebook page is available here.