leetcode

Longest Substring Without Repeating Characters solution using TypeScript

Below is my TypeScript solution to the LeetCode "Longest Substring Without Repeating Characters" question.

Time Complexity: Because each character in the string will be visited only one time, the time complexity is O(n), where n represents the number of characters in the string.

Space Complexity: This approach will place one entry in a hash map for every character in the string in the worst case. This makes the space complexity O(n).

/**
 * Find the length of the longest substring that does
 * not contain any repeating characters in a given string.
 *
 *   Time Complexity: O(n)
 *   Space Complexity: O(n)
 *
 *   Input: "abcabcbb"
 *   Output: 3 
 *   Explanation: "abc" has a length of 3.
 */
function lengthOfLongestSubstring(s: string): number {
    // map a character to its index in the array
    let map: Map<string, number> = new Map([]);
    let longest = 0; // longest substring found
    let length = 0; // length of the substring currently being calculated

    for(let i = 0; i < s.length; i++) {
        const encountered = map.get(s[i]);
        if (encountered === undefined) {
            length += 1;
        } else {
            length = Math.min(i - encountered, length + 1);
        }
        longest = Math.max(longest, length);
        map.set(s[i], i);
    }
    return longest;
}

more LeetCode posts