Now I have solved this algorithmic challenge myself but I would like someone to explain the answer below line by line please as I took it from someone else. I do NOT understand it at all and how the answers come to be, even after using pythonTutor.
Challenge:
Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.
Edit: I only do NOT understand the ABOVE CODE.
function findLongestSubstring(str) {
let longest = 0;
let seen = {};
let start = 0;
for (let i = 0; i < str.length; i++) {
let char = str[i];
if (seen[char]) {
start = Math.max(start, seen[char]);
}
// index - beginning of substring + 1 (to include current in count)
longest = Math.max(longest, i - start + 1);
// store the index of the next char so as to not double count
seen[char] = i + 1;
}
return longest;
}
// findLongestSubstring("thisisawesome"); // 6
// findLongestSubstring("thecatinthehat"); // 7
My solution:
function findLongestSubstring(str){
if (str.length === 0) return 0;
// track longest length
let longestLength;
// get first subArr
let subStrArr = str.split("").slice(0,1);
// get first subArrLength
let subStrLength = subStrArr.length;
longestLength = subStrLength;
// variable for checking every character
let j = 0;
// for loop
for ( let i = 1; i < str.length; i++ ) {
// if current element don't exist in subArr
if (!subStrArr.includes(str[i])) {
subStrArr = str.split("").slice(j,i+1);
subStrLength = subStrArr.length;
}
// does exist
else {
j++;
i = j;
subStrArr = str.split("").slice(i,i+1);
subStrLength = subStrArr.length;
}
if (subStrLength > longestLength) longestLength = subStrLength;
}
return longestLength;
}
findLongestSubstring("rithmschool"); // 7
A substring with unique characters doesn't obviously have duplicate letters. So as we move forward in our string str, we keep track of the greatest index of all the characters that we have already met in seen. The greatest index of each letter is obviously the one we have seen last since we move from left to right.
Now, in your iteration, when you reach a letter that you find in seen, you need to set start to that character's index tracked by seen to avoid including both letters in your substring. We take the max because start of substring may already be higher because of another double letter that we met earlier:
if (seen[char]) {
start = Math.max(start, seen[char]);
}
Then we just look how long our current substring is and retain it if it's longer than our longest seen.
longest = Math.max(longest, i - start + 1);
And at last we save the index of the character in seen
seen[char] = i + 1;
The order of these operations is important. If we updated seen with the index of the char first then we couldn't check seen for the character and set start based on it.