## Issue

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

## Solution

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?

Answered By – see sharper

Answer Checked By – David Goodson (BugsFixing Volunteer)