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;
}