arcbjorn

thoughtbook

RSS Feed

Saturday, February 25, 2023

Longest substring without repeating characters

Leetcode 3 problem.

Typescript

  • Time complexity: O(n)O(n) - n is a length of a string
  • Auxiliary space: O(n)O(n) - n is a length of a string
function lengthOfLongestSubstring(s: string): number {
  let longestStringLength = 0;
  let currentPosition = 0;

  let counter = 0;
  let characterSet = new Set();

  while (currentPosition < s.length) {
    if (characterSet.has(s[currentPosition])) {
      characterSet.delete(s[counter++]);
    } else {
      characterSet.add(s[currentPosition++]);
      longestStringLength = Math.max(
        longestStringLength,
        characterSet.size,
      );
    }
  }

  return longestStringLength;
}
Creative Commons Licence