JavaScript/Dynamic-Programming/Sliding-Window/LongestSubstringWithoutRepeatingCharacters.js at master · Guduly/JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 * These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 * Sliding window technique reduces the required time to linear O(n).
 * @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
exportfunctionLongestSubstringWithoutRepeatingCharacters(s){
letmaxLength=0
letstart=0
letend=0
constmap={}
while(end<s.length){
if(map[s[end]]===undefined){
map[s[end]]=1
maxLength=Math.max(maxLength,end-start+1)
end++
}else{
while(s[start]!==s[end]){
deletemap[s[start]]
start++
}
deletemap[s[start]]
start++
}
}
returnmaxLength
}

// Example 1:
// Input: s = "abcabcbb"
// Output: 3
// Explanation: The answer is "abc", with the length of 3.

// Example 2:
// Input: s = "bbbbb"
// Output: 1
// Explanation: The answer is "b", with the length of 1.

// Example 3:
// Input: s = "pwwkew"
// Output: 3
// Explanation: The answer is "wke", with the length of 3.
// Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.