What is the time complexity of this code? lengthOfLongestSubstring

Question

Could you please help me with the time complexity of the code below?

This is a leet code problem - the function should take a string as input and return the length of the longest substring with non-repeating characters:

• input "abcabcbb" returns 3 as answer is 'abc'
• input "bbbbb" returns 1 as answer is 'b'
• input "pwwkew" returns 3 as answer is 'wke'

This can be solved with a sliding window technique which if implemented well is O(n). My initial solution shown below is sliding windowish, but my solution is not O(n) as there is an inner loop triggering sometimes and this inner loop is not required at all.

In short there is a nested loop, outer loop runs for every character of the input string. The inner loop will run every time a duplicate character is hit, and it will run as many times as the number of characters between the current character and the previous occurence of this character, so:

• input "abcabcbb", outer loop will execute 8 times as there are 8 characters, inner loop will trigger when it hits the second occurence of letter 'a' ("abcabcbb") and will run 2 times for b, c (letters in-between), then will trigger for second occurence of letter 'b' ("abcabcbb") and will run 2 times for c, a, then will trigger for letter 'c' ("abcabcbb") and run 2 times for a, b, then again letter 'b' ("abcabcbb") and run once for c. It will then hit the final letter "b" which is again a duplicate, but since there are no characters in-between, it will not execute any loop.
• I assume the worst case is when I just keep repeating a string. With input string "abcdefghabcdefgh" or more readable, "abcdefgh + abcdefgh" outer would execute 16 times for every character, inner loop would run 8 times when it starts hitting the duplicate letters, each time with 7 iterations.
• So if we switch "abcdefgh" to large or infinite nr. of unique characters put together (m), and the full input string is (m + m + m + ...repeated infinitely many times), and the input length is the letter n, then:
• outer loop: runs n times
• inner loop: runs (n - m) * (m-1) // I'm just looking at the previous examples and the relationships there
• n * ((n-m) * (m-1)) // put together
• n * ((n-m) * (m)) // removing -1 constant
• n * (nm - m^2) // simplifying
• So O(n * (nm - m^2))? Or just simple O(n^2)? Or maybe O(n * m)? What is the right answer?

Code:

var lengthOfLongestSubstring = function(str) {
    // Create storage object for caching
    let storage = {
        longestSubStringLength: 0,
        longestSubString: 0,
        cache: {
            subString: ''
        }
    };
    // Loop through string
    for (let i = 0; i < str.length; i++) {
        let char = str[i];
        if (!storage.cache[char] && storage.cache[char] !== 0) {
            // If current letter is not in storage, add it and extend current substring
            storage.cache[char] = i;
            storage.cache.subString += char;
        } else {
            // If current letter is already in storage, start a new round
            let previousCache = storage.cache;
            storage.cache = {
                subString: ''
            };
            if (previousCache[char] + 1 !== i) { // If there are letters in-between
                storage.cache.subString = str.substring(previousCache[char] + 1, i);
                for (let j = previousCache[char]; j < i; j++) {
                    storage.cache[str[j]] = j;
                }
            }
            storage.cache[char] = i;
            storage.cache.subString += char;
        }
        // If current substring is the longest, update it in storage
        if (storage.cache.subString.length > storage.longestSubStringLength) {
            storage.longestSubStringLength = storage.cache.subString.length;
            storage.longestSubString = storage.cache.subString;
        }
    }
    return storage.longestSubStringLength;
};

Answer 1

We could do jsperf on this Map version

Time complexity of O(n) because a single pass through the string.

Space complexity is O(min(m, n)), where m is the size of the character set, due to storing the characters and their indices in a map.

It is however a lot more readable

const lengthOfLongestSubstring = str => {
    let cnt = 0;
    let n = str.length;
    let answer = 0;
    let map = new Map(); // to store the strings and their length
    for (let start = 0, end = 0; end < n; end++) { // slide
      // move start if the character is already in the map
      if (map.has(str[end])) start = Math.max(map.get(str[end]), start);
      answer = Math.max(answer, end - start + 1); // longest string
      map.set(str[end], end + 1);
      cnt++
    }
    return [str, `lookups: ${cnt} lookups:`, "answer", answer];
  }
  ["abcabcbb", "bbbbb", "pwwkew", "abcdefghabcdefgh"].forEach(str => console.log(lengthOfLongestSubstring(str).join(" ")))