Find the longest substring in a given string.

 

Find the longest substring in a given string.

Agoda round 1 on 31/05/2023 by Peter and Kuma

Example #1:

input: 'abcabc'

output: 3

Example #2:

input: 'bbbb'

output: 1

Example #3:

input: 'abb'

output: 2

function solution(s) {

const strLen = s.length;

let max = 0;

let long = []; // b

for(let j=0; j < strLen; j++) { // j = 1, b

if (long.indexOf(s[j]) > -1) {

long = [];

// push the curr char to the long list

long.push(s[j]);

} else {

// push the curr distinct char to the long list

long.push(s[j]);

const longLen = long.length;

if (longLen > max) {

max = longLen;

}

}

}

return max;

}

// Time complexity can be improved to O(n) by putting characters of the longest

substring ('long' in the above code) in a map instead of list.

/*{

p: 1,

w: 1,

}*/

// Time O(n^2)

// "pwwkew" -> [p ,w, w, k , w, e, w]

// max = 2

// long = [w];