LeetCode Longest Substring Without Repeating Characters
Problem statement
Given a string s, find the length of the longest substring without repeating characters.
Problem statement taken from: https://leetcode.com/problems/longest-substring-without-repeating-characters
Example 1:
Input: s = 'abcabcbb'
Output: 3
Explanation: The answer is 'abc', with the length of 3.
Example 2:
Input: s = 'bbbbb'
Output: 1
Example 3:
Input: s = 'pwwkew'
Output: 3
Example 4:
Input: s = ''
Output: 0
Constraints:
- s consists of English letters, digits, symbols and spaces.
- 0 <= s.length <= 5 * 10^4
Explanation
Brute force
A brute force solution will be to iterate through all possible substrings of the input string. Let's say we have a function checkUniqueString which returns true or false based on a string that has all unique characters or not.
We generate all possible substrings using two nested for loops and inside which we call checkUniqueString function.
A small code block in C++ will look like this.
int n = s.length();
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
if (checkUniqueString(s, i, j)){
// logic for updating the max length substring
}
}
}
checkUniqueString will iterate over the string once to check for any repeating character. Hence it will take O(N) time.
The above two nested for loops will take O(N²) time. The total time complexity is O(N3).
Sliding Window
The sliding window approach is widely used in many arrays and string problems. The above brute force approach can be optimized using a sliding window.
A sliding window is a range of elements in the array/string that is defined by start and end indices, i.e., [i, j) (left index included, right index excluded). The window can be used to slide its range in a certain direction. So if we right shift the window to right by 1 element then [i, j) will change to [i + 1, j + 1).
Algorithm
Initially, the window size is 0 as we have pointed left and right at the first index. We keep on incrementing right till we find a repeated character in the string. When right finds a repeated character, we found the maximum size of substrings without duplicate characters starting at index left.
We keeping doing for all elements of the string till we reach the end.
- Initialize variables left, right, and ans to 0.
- Create an array named as chars of length 128.
This will store the number of times an element appeared in an array.
- Loop while ( right < s.length() )
- set char r = s[right]
- increment chars[r]++
- Loop while ( chars[r] > 1 )
- set char l = s[left]
- decrement chars[l]--
- increment left++
- set maximum till now in ans.
ans = max(ans, right - left + 1)
- increment right++
- return ans
The time complexity of the above solution is O(N).
Optimized sliding window
The above solution can be optimized further. Instead of iterating over each index of the string, we define a mapping of the characters to its index. Then we skip all the characters immediately when we find a repeated character.
C++ solution
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
unordered_map<char, int> map;
for(int i = 0, j = 0; j < s.size(); j++){
if(map.find(s[j]) != map.end()){
i = max(map[s[j]], i);
}
ans = max(ans, j - i + 1);
map[s[j]] = j + 1;
}
return ans;
}
};
Golang solution
func lengthOfLongestSubstring(s string) int {
m := make(map[byte]int)
i, ans := 0, 0
for j := 0; j < len(s); j++ {
if v, ok := m[s[j]]; ok {
if v > i {
i = v
}
}
if j - i + 1 > ans {
ans = j - i + 1
}
m[s[j]] = j + 1
}
return ans
}
Javascript solution
var lengthOfLongestSubstring = function(s) {
var mapping = {};
var i = 0;
var ans = 0;
for(var j = 0; j < s.length; j++){
if(mapping[s[j]]) {
if(mapping[s[j]] > i) {
i = mapping[s[j]];
}
}
if(j - i + 1 > ans){
ans = j - i + 1;
}
mapping[s[j]] = j + 1;
}
return ans;
};
Let's dry-run our algorithm to see how the solution works.
s = 'abcdeafb'
m = map()
ans = 0
Step 1: i = 0, j = 0
s[j] = 'a'
m['a'] = j + 1 = 1
ans = max(ans, j - i + 1) = max(0, 0 - 0 + 1) = 1
Step 2: i = 0, j = 1
s[j] = 'b'
m['b'] = j + 1 = 2
ans = max(ans, j - i + 1) = max(1, 1 - 0 + 1) = 2
Step 3: i = 0, j = 2
s[j] = 'c'
m['c'] = j + 1 = 3
ans = max(ans, j - i + 1) = max(2, 2 - 0 + 1) = 3
Step 4: i = 0, j = 3
s[j] = 'd'
m['d'] = j + 1 = 4
ans = max(ans, j - i + 1) = max(3, 3 - 0 + 1) = 4
Step 5: i = 0, j = 4
s[j] = 'e'
m['e'] = j + 1 = 5
ans = max(ans, j - i + 1) = max(4, 4 - 0 + 1) = 5
Step 6: i = 0, j = 5
s[j] = 'a'
m['a'] is 1
set i = max(i, m['a']) = max(0, 1) = 1
ans = max(ans, j - i + 1) = max(5, 5 - 1 + 1) = 5
m['a'] = 6
Step 7: i = 1, j = 6
s[j] = 'f'
m['f'] = j + 1 = 7
ans = max(ans, j - i + 1) = max(5, 6 - 1 + 1) = 6
Step 8: i = 1, j = 7
s[j] = 'b'
m['b'] is 2
set i = max(i, m['a']) = max(1, 2) = 2
ans = max(ans, j - i + 1) = max(6, 7 - 2 + 1) = 6
So the answer is 6.