Task
Task:
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", which the length is 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.
This problem was taken from Leetcode
Solution
The sliding window solution.
The sliding window represents a range of elements like an array, defined by the start and end indices. Then we start moving “sliding” the indices to the next checked subset.
Let’s say that we have this string: “ABCDECFGH”.
The answer of the problem is “DECFGH“.
The obvious resolution could be to grab each letter of the string (starting with the first one), compare it with a buffer of the letters that we already checked and if there is match, continue with the next letter and keep track of the length of the longest string sequence without repeated characters.
In the current example “ABCDECFGH” let’s name is S we start with starting index i = 1, and end index j = 1. so S[i, j)
Then we start “sliding” j adding more elements in the range and comparing next element added in the range with all previous elements till we find match. I our example this will happen on i = 1 and j = 6 since 6th letter is C and C is already in the range at position 3. Let’s call it j1 = 3.
Then the next step will be to “slide” i and start all over. i = i + 1.
But we could improve this algorithm in two ways:
- Store the characters in the buffer into an associative array or so called hashmap where the key will be the character, and the value the index. Example:
{ key = A, val = 1 }
{ key = B, val = 2 }
…
This way we don’t have to iterate through each element into the buffer when checking if the character is there or not. - When we find match, we don’t have to start from the next character but we can “slide” to the value of the character in the buffer that matched + 1 since we already know, that the sequence before has shorter length.
In the range [i, j1] which in the current example is [1, 3] we know for sure that there will be no substring longer than the current one [i, j] so we don’t have to “slide” i = i + 1 but we could do i = j1 + 1 which will save checking of [i+1, j1] (B and C)
Example:
start checking ABCDE and then C is already found in the buffer at index = 3. So instead of starting from index 2 – B we could start from index 3 + 1 which is D
The solutions:
Java Script
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var hashMap = {};
function findUniqueSequence(left) {
var buffer = [];
for(var c = left;c < s.length; c ++) {
if(buffer.includes(s[c])) {
var symbol = s[c];
var nextPos = hashMap[symbol] + 1;
return [buffer, nextPos ];
}
hashMap[s[c]] = c;
buffer.push(s[c]);
}
return [buffer, s.length];
}
var left = 0;
var longest = [];
while(left < s.length) {
var result = findUniqueSequence(left);
left = result[1];
longest = longest.length < result[0].length ? result[0] : longest;
if(s.length - left < longest)
break;
}
return longest.length;
};
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unsigned long n = s.length();
char char_array[n+1];
strcpy(char_array, s.c_str());
int left = 0;
unsigned long arr_length = sizeof(char_array) - 1;
int longestStringSize = 0;
int sizeCounter = 0;
std::map<char, int> buffer;
int co = 0;
while (left < arr_length) {
char cursor = char_array[left];
if(buffer[cursor] == 0) {
buffer[cursor] = left + 1;
sizeCounter ++;
left ++;
}
else {
left = buffer[cursor];
buffer.clear();
longestStringSize = sizeCounter > longestStringSize ? sizeCounter : longestStringSize;
sizeCounter = 0;
}
}
longestStringSize = (longestStringSize == 0 || sizeCounter > longestStringSize) ? sizeCounter : longestStringSize;
return longestStringSize;
}
};
