Can my algorithm be considered as O(n)? "Finding the longest substring with unique characters"

Question

I stumbled upon this excercise:

Create a function that returns the longest substring with unique characters.

and I'm just wondering if I have accomplished O(n) time complexity with the solution I came up with.

i.e:

getMaxSubStr("linkshortener") -> "linkshorte"

there's only one for loop no nesting so this should be O(n) right, what's giving me doubts is that when tempStr stumbles a repeating character the iterator goes back to the string index of where the repeating character is last seen, so that adds to the runtime operations needed to be done and not sure if it's still O(n)

async function maxUniqueStr(string) {
  let maxStr = "";
  let tempStr = "";
  let lastSeen = {};

  for (let i = 0; i < string.length; i++) {
    let char = string.charAt(i);

    if (tempStr.includes(char)) {
      i = lastSeen[char];
      tempStr = "";
      console.log("-continue-", i);
      continue;
    }

    tempStr += char;
    maxStr = tempStr.length > maxStr.length ? tempStr : maxStr;
    lastSeen[char] = i;  
  }

  return maxStr;
}

should the substring start from start, or could it been inbetween? — Nina Scholz, Aug 06 '19 at 09:59
`tempStr.includes` this adds extra iterations, so, no your fuction is not `O(n)` — Liam, Aug 06 '19 at 10:01
could be anywhere as long as that substr is the longest substr with unique characters i.e. datastructures -> astruc — Dwyte, Aug 06 '19 at 10:02
Also `lastSeen[char]` is a `O(n log n)` operation too as it's a [hashtable lookup](https://stackoverflow.com/a/7374472/542251). You never going to be able to do this in a true O(n) performance. TBH I doubt that really matters either. Why do you care? — Liam, Aug 06 '19 at 10:04
oh I thought accessing on objects is O(1).. anyway was just wondering what could be improved upon on the algo to be efficient as possible cause I'm currently taking an algo&ds course rn, and that's part of an excercise hehe — Dwyte, Aug 06 '19 at 10:28

גלעד ברקן · Answer 1 · 2019-08-06T19:07:44.557

I like the two pointer approach:

function f(S){
  let maxLength = 1
  let idx = 0
  let l = 0
  let r = 1
  let set = new Set([S[0]])

  for (; l<S.length-1, r<S.length;){
    if (!set.has(S[r]))
      set.add(S[r++])
    else
      set.delete(S[l++])
    let currLength = r - l
    if (currLength > maxLength){
      maxLength = currLength
      idx = l
    }
  }
  return S.substr(idx, maxLength)
}

console.log(f('asaafg'))

Can my algorithm be considered as O(n)? "Finding the longest substring with unique characters"

1 Answers1