I am working on solving an algorithm problem whose prompt is this:
"Given a string s, find the length of the longest substring without repeating characters."
I have two accepted solutions shown below:
function lengthOfLongestSubstring(s: string): number {
let longestStr = '';
let maxLength = 0;
for (let i = 0; i < s.length; i += 1) {
//solution 1
if (longestStr.split('').includes(s[i])) {
longestStr = longestStr.slice(longestStr.split('').indexOf(s[i]) + 1);
}
longestStr += s[i];
if (longestStr.length > maxLength) {maxLength = longestStr.length}
// solution 2
longestStr += s[i];
if(longestStr.indexOf(s[i]) !== longestStr.length - 1) {
longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1)
}
if (longestStr.length > maxLength) {maxLength = longestStr.length}
}
return maxLength;
}
The difference between the two solutions is whether to introduce this code before or after the if statements.
longestStr += s[i];
The only difference in code that would contribute to time/space complexity is the code inside the respective if statements.
Solution 1 has much better performance: 214ms, 44.9MB
Solution 2 significantly worse: 607ms, 47MB
Solution 1:
According to Running time of string.Split method , .split method has O(n) time complexity.
.includes method must have O(n) since it loops once.
Solution 2:
According to What is the time complexity of javascript's array.indexOf?, .indexOf has O(n).
.length is a method accessible inside all enumerable Javascript objects(arrays), and look up in an array is O(1).
Unless my above time complexities are incorrect, it seems like solution 2 would take less time. However, it is the total opposite.
Please help me understand, thanks
You're right. Solution 1 should perform much worse. And it does, at least according to my tests:
function lengthOfLongestSubstring(s) {
let longestStr = ''
let maxLength = 0
for (let i = 0; i < s.length; i += 1) {
//solution 1
if (longestStr.split('').includes(s[i])) {
longestStr = longestStr.slice(
longestStr.split('').indexOf(s[i]) + 1
)
}
longestStr += s[i]
if (longestStr.length > maxLength) {
maxLength = longestStr.length
}
}
return maxLength
}
function lengthOfLongestSubstring2(s) {
let longestStr = ''
let maxLength = 0
for (let i = 0; i < s.length; i += 1) {
// solution 2
longestStr += s[i]
if (longestStr.indexOf(s[i]) !== longestStr.length - 1) {
longestStr = longestStr.slice(longestStr.indexOf(s[i]) + 1)
}
if (longestStr.length > maxLength) {
maxLength = longestStr.length
}
}
return maxLength
}
let s1 = ''
const slen = 1000000
const letters = 'abcdeghijklmnop'
for (let i = 0; i < slen; i++) {
s1 = s1 + letters[Math.random() * letters.length]
}
console.time('solution1')
console.log(lengthOfLongestSubstring(s1))
console.timeEnd('solution1')
console.time('solution2')
console.log(lengthOfLongestSubstring2(s1))
console.timeEnd('solution2')
// result: solution 1: 1.484s, solution 2: 317ms
Do you see the same thing?