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

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)