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