# [SOLVED] Why does two seemingly similar array methods result in drastically different time complexity?

## 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.

## 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?