Longest Substring Without Repeating Characters solution using TypeScript


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

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.

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