code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

003 Longest Substring Without Repeating Characters

/**
 * 
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

 /* 
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 */
function longestSubstringWithoutRepeatingCharacters(value) {
  let windowChars = {} // {a: 0, b: 1, c: 2}
  let windowStart = 0
  let maxCount = 0
  for (let index = 0; index < value.length; index++) {
    const endChar = value[index];
    if(windowChars[endChar] >= windowStart){
      windowStart = windowChars[endChar] + 1
    }
    windowChars[endChar] = index
    maxCount = Math.max(maxCount, index - windowStart +  1)
  }  
  return maxCount
}

test('longest Substring Without Repeating Characters', () => {
  expect(longestSubstringWithoutRepeatingCharacters('abcabcbb')).toEqual(3)
});

Created 2020-02-23T08:56:10+00:00, updated 2020-02-23T16:58:11+00:00 · History · Edit