# LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: `get` and `put`.

`get(key)` – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
`put(key, value)` – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Could you do both operations in O(1) time complexity?

Example:

```LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4
```

This problem was taken from Leetcode

## Solution

The brute force solution will be to use array, to push every new element at the top, and on ‘get’ to pop out the element and to put it at the top of the array.

A better solution will be to use hashmap where the element retrieval will be O(1) (constant) but the hashmap is not keeping track of the order of the elements. To solve this problem we are going to link elements in the hashnmap table with double linked list, where each element will point to its previous and next sibling.
On every ‘get’ operation we are going to re-link the element and it’s siblings.

When the cache reaches the capacity we are going to remove the least used node from the bottom.

 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) return 1 -1 -1 3 4 result 1 2,1 1,2 3,1 => (2) 3,1 4,3 => (1) 4,3 3,4 4,3

```class LRUCache {

constructor(capacity) {

this.tail = null;
this.capacity = capacity;
this.count = 0;
this.hashMap  = new Map();
}

get(key) {
var node = this.hashMap.get(key);
if(node) {
return node.val;
}
if(this.tail == node && this.tail.prev) {
// if the node is at the tail,
// set tail to the previous node if it exists.
this.tail = this.tail.prev;
this.tail.next = null;
}
if(node.prev)
node.prev.next = node.next;
if(node.next)
node.next.prev = node.prev;
node.prev = null;

return node.val;
}
return -1;
}

put(key, val) {
this.count ++;
var newNode = { key, val, prev: null, next: null };

// this.hashMap is empty creating new node
this.tail = newNode;
}
else {
var oldNode = this.hashMap.get(key);
if(oldNode) {
// if node with the same key exists,
// clear prev and next pointers before deleting the node.
if(oldNode.next) {
if(oldNode.prev)
oldNode.next.prev = oldNode.prev;
else
}
if(oldNode.prev) {
oldNode.prev.next = oldNode.next;
if(oldNode == this.tail)
this.tail = oldNode.prev;
}
// removing the node
this.hashMap.delete(key);
this.count --;
}

// adding the new node and set up the pointers to it's neibouring nodes

if(this.tail == null)

if(this.count == this.capacity + 1) {
// remove last nove if over capacity
var lastNode = this.tail;
this.tail = lastNode.prev;
if(!this.tail) {
//debugger;
}
this.tail.next = null;
this.hashMap.delete(lastNode.key);
this.count --;
}

}
this.hashMap.set(key, newNode);
return null;
}
}```

# Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

image was borrowed from leetcode

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input:

``` [0,1,0,2,1,0,1,3,2,1,2,1]
```

Output:

` 6`

This problem was taken from Leetcode

## Solution

The brute force approach: for each element we go to the right and find the maximum height of the bar, then we go to the left and do the same.

For any element the maximum amount of the water that could be trapped will be the minimum of left height and right height, minus the height of the bar.

So for the array [0,1,0,2,1,0,1,3,2,1,2,1] we go all the way to the right and calculate the max right value, starting from first element ‘0’ max right will be 0. ‘1’ – max right is ‘1’ and so on.
We repeat the same from last element ‘1’ to the first one.

Then the trapped water for the first column will be:  min(maxRight, maxLeft) – theArrayElement[n]

 the array 0 1 0 2 1 0 1 3 2 1 2 1 max right 0 1 1 2 2 2 2 3 3 3 3 3 max left 3 3 3 3 3 3 3 3 2 2 2 1 collected water 0 0 1 0 1 2 1 0 0 1 0 0

The complexity will be O(n2)

```/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
if(height.length < 2)
return 0;

let findMaxLeft = function(idx, height) {
let max = 0;
for(let i =idx;i >= 0; i --) {
max = Math.max(max, height[i]);
}
return max;
}

let findMaxRight = function(idx, height) {
let max = 0;
for(let i = idx;i < height.length; i ++) {
max = Math.max(max, height[i]);
}
return max;
}

let collectedWater = 0;
for(let i = 0;i < height.length; i ++) {

const maxLeft = findMaxLeft(i, height);
const maxRight = findMaxRight(i, height);

let min = Math.min(maxLeft, maxRight);
collectedWater += (min - height[i]);
}

return collectedWater;
};```

The better solution: find all max left and max right with one loop, then do a second loop for each element in the array, and calculate trapped water.

```/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let maxLeftArray = [], maxRightArray = [];
let maxLeft = 0, maxRight = 0;
const ln = height.length;
let trappedWater = 0;

for(let i = 0;i < height.length; i ++) {
maxLeftArray[i] = Math.max(height[i], maxLeft);
maxLeft = maxLeftArray[i];

maxRightArray[ln - i - 1] = Math.max(height[ln - i - 1], maxRight);
maxRight = maxRightArray[ln - i - 1];
}

for(let i = 0;i < height.length; i ++) {
trappedWater += Math.min(maxLeftArray[i], maxRightArray[i]) - height[i];
}
return trappedWater;

};```
what we just did:

– With one loop find the max left and right bar on each side.
– for any element the maximum amount of the water that could be trapped will be the minimum of left height and right height, minus the height of the bar.

# Array VS Hash Table

Hash table tutorial

Find element in Array

```function fuindInArray() {
var t0 = performance.now();

for(var q = 0; q < data2.length; q++) {
if( data2[q] == '106112407') {
console.log(data2["106112407"]);
break;
}
}```

Find element in Hash Table

```function findInHashtable() {
var t0 = performance.now();

console.log(data1["106112407"]);

var t1 = performance.now();
document.querySelector('#result1').value = "Call took " + (t1 - t0) + " milliseconds.";
}```

# Majority element in array

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input:

``` [3,2,3]
```

Output:

` 3`

Example 2:

Input:

``` [2,2,1,1,1,2,2]
```

Output:

``` 2
```

This problem was taken from Leetcode

## Solution

The solution:

Create an object (or associative array, depends of the language), iterate through all elements in the array adding them to the newly created object using the element value as a key. If element exists increase the value +1.
Keep track of mostly repeated element and return it at the end.

```var arr = [3, 3, 4, 2, 4, 2, 4, 4];

/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
var elements = {};
var majorityElement = nums[0];
var majorityElementCount = 1;
for(var i in nums) {
var element = nums[i];
elements[element] = typeof elements[element] == 'undefined' ? 1 : elements[element] + 1;
if(elements[element] > majorityElementCount) {
majorityElement = element;
majorityElementCount = elements[element];
}
}
return majorityElement;
};

console.log(">>", majorityElement(arr));```

– Create an object (line 9)
– Iterate through each element in the array feeling up the object with the elements from the array where the element value would be the key of the element (line 14)
– Each time when the element exists, add + 1
– Keep track of mostly repeated element (Lines 16-17)

Could we optimize the code? Slightly. When we add + 1 we could check if the value is already greater than the length of the array / 2 and if se we know that this is the majority element because no other element could have greater value.

```...
if(elements[element] > nums.length / 2) {
return element;
}
...```

# Maximum Subarray

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input:

``` [-2,1,-3,4,-1,2,1,-5,4],
```

Output:

``` 6
```

Explanation:

``` [4,-1,2,1] has the largest sum = 6.
```

This problem was taken from Leetcode

The solution:

## Brut force.

The straight forward solution could be to iterate through all elements in the array and calculate the subarray values and compare them.

In the example above[-2,1,-3,4,-1,2,1,-5,4] we will do:

starting index: 1
-2 = -2
-2, 1 = -1
-2, 1, -3 = -4
-2, 1, -3, 4 = 0
-2, 1, -3, 4, -1 = -1
-2, 1, -3, 4, -1, 2 = 1
-2, 1, -3, 4, -1, 2, 1 = 2
-2, 1, -3, 4, -1, 2, 1, -5 = -3
-2, 1, -3, 4, -1, 2, 1, -5, 4 = 1

starting index: 2
1 = 1
1, -3 = -2
1, -3, 4 = 2
1, -3, 4, -1 = 1
1, -3, 4, -1, 2 = 3
1, -3, 4, -1, 2, 1 = 4
1, -3, 4, -1, 2, 1, -5 = -1
1, -3, 4, -1, 2, 1, -5, 4 = 3

starting index: 3
-3 = -3
-3, 4 = 1
-3, 4, -1 = 0
-3, 4, -1, 2 = 2
-3, 4, -1, 2, 1 = 3
-3, 4, -1, 2, 1, -5 = -2
-3, 4, -1, 2, 1, -5, 4 = 2

starting index: 4
4 = 4
4, -1 = 3
4, -1, 2 = 5
4, -1, 2, 1 = 6
4, -1, 2, 1, -5 = 1
4, -1, 2, 1, -5, 4 = 5

… and so on till the last element in the array.

So the winner clearly is 4, -1, 2, 1 = 6, but this approach will take a lot of repetitions. Interestingly there is a linear solution called: Kadane’s algorithm.

The basic idea of this algorithm is to break the array into a sets of mutually exclusive sets, calculate their sums and find the largest one.

First let’s look closely of what we are doing to find the maximum sum using brut force. We are splitting the array to a sets of all possible contiguous sub arrays and we calculate their sum. This means that:
– if the array contains only negative values we don’t really need to split the array cause the answer will be the largest value in the array. i.e. [-1,-5,-3] = -1 (the one close to 0)
– if this is a mixed array with negative and positive values the max sum of contiguous sub array will be > 0 so we could ignore any case where the sum is negative.

This way we could iterate through each element of the array `nums[i]`  where i is the index of the element in the array (starting with the first one `nums[0]`), and calculate the sum (let’s call it `max_here = max_here + nums[i]` ).
If we get a negative result we already know for sure that this is not what we are looking for and we set up `max_here` to the next element in the array `max_here = nums[i]`

So in the example above: [-2,1,-3,4,-1,2,1,-5,4]
We are starting by setting up both params to the first element in the array: `max_here =``max_so_far = nums[0]` . We are going to use `max_so_far` to store the maximum sum discovered so far, and `max_here` to calculate the maximum sum so far. Once again if the `max_sum` is negative, we just set it up to be equal to the next element in the array `nums[i]` so on the next iteration `max_sum = nums[i-1] + nums[i]`

Starting with setting up `max_here = max_so_far = nums[0] = -2`

 i nums[i] action described max_here max_so_far 1 1 `sum = max_here + nums[1]`, which is: `sum = -2 + 1 = -1` which is smaller than `nums[1]` so `max_here = nums[1] = 1` (line 10 in the code snipped below) and since `max_here > max_so_far`,  `max_so_far = max_here =1` (line 11) 1 1 2 -3 `sum = max_here + nums[2]` which is: `sum = 1 + (-3) = - 2` which is bigger than `nums[2]` which is -3 so `max_here = sum = -2`But `max_here` is smaller than `max_so_far` so `max_so_far` stays equal to 1 -2 1 3 4 `sum = -2 + 4 = 2` which is < than 4 so  `max_here = nums[4] = 4` which is > `max_so_far` so `max_so_far = max_here = 4` 4 4 4 -1 `sum = 4 - 1 = 3` > – 1 so `max_here = sum = 3` 3 4 5 2 `sum = 3 + 2 = 5` which is > than `nums[5] = 2` so `max_here = max_so_far = sum = 5` 5 5 6 1 `sum = 5 + 1 = 6` which is > than `nums[6] = 1` so `max_here = max_so_far = sum = 6` 6 6 7 -5 `sum = 6 + (-5) = 1` which is > than `nums[7] = -5` so `max_here = 1` 1 6 8 4 `sum = 1 + 4 = 5` which is > than `nums[8] = 4` so `max_here = 5` but `max_here < max_so_far` so `max_so_far` stays the same: 6 which is the maximum sum here. 5 6

```/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var max_here = max_so_far = nums[0];

for(var i=1;i < nums.length; i ++) {
max_here = Math.max(max_here + nums[i], nums[i]);
max_so_far = Math.max(max_so_far, max_here);
}

return max_so_far;
};```

# Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input:

``` [1,2,3]
```

Output:

``` [1,2,4]
```

Explanation:

``` The array represents the integer 123.
```

Example 2:

Input:

``` [4,3,2,1]
```

Output:

``` [4,3,2,2]
```

Explanation:

``` The array represents the integer 4321.
```

This problem was taken from Leetcode

## Solution

The solution:

The solution is pretty straight forward. We traverse all digits in the opposite direction, and make sure that we add +1 only on the last digit (the first iteration ). Then if the digit > 9 we set up the dit to 0, and we carry on 1 to add it to the next digit, and keep going till we reach the first digit. If the first digit is 9 and cary over is not 0, we add 1 to the beginning of the array.

let’s consider: 9 9 9

iteration 1:
9            9
9            9
9 + 1 =  0 + cary on: 1

iteration 2:
9            9
9 + 1 =  0 + cary on: 1
0            0

iteration 3:
9 + 1 = 0 + cary on: 1
0          0
0          0

finally:
0
0
0

which gave up the final result: 1 0 0 0

The solution will look like this:

Java Script

```/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {

var carryOn = 0;
for(q = digits.length - 1; q!=-1; q--) {
var digit = digits[q];
if(q == digits.length - 1) {
digit = digit + 1;
if(digit == 10) {
digit = 0;
carryOn = 1;
}
}
else {
if(digit == 9 && carryOn) {
digit = 0;
}
else {
digit = digit + carryOn;
carryOn = 0;
}
}
digits[q] = digit;
}
if(carryOn > 0)
digits.unshift(1);
return digits;
};```

what we just did:
– (lines 11 – 18) happened only if this is the last digit, where we have to add 1
– (lines 18 – 20) if we have carry on value of `carryOn > 0` and `digit = 9` simply set `digit = 0` and left `carryOn` to be equal to 1 for the next iteration.

# Valid Parentheses

Given a string containing just the characters `'('``')'``'{'``'}'``'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input:

``` "()"
```

Output:

``` true
```

Example 2:

Input:

``` "()[]{}"
```

Output:

``` true
```

Example 3:

Input:

``` "(]"
```

Output:

``` false
```

Example 4:

Input:

``` "([)]"
```

Output:

``` false
```

Example 5:

Input:

``` "{[]}"
```

Output:

` true`

This problem was taken from Leetcode

## Solution

The solution:

Let’s look at the simplest scenario where we have only one type of brackets: ‘(‘ and ‘)’. Then all that we need to do in order to figure out if each bracket has corresponding closing bracket is to put each opening bracket into a stack, and pop one bracket when we see closing bracket.

Ideally if the brackets are “normalized” (all of the open one have corresponding closing brackets) we will end up with empty stack.

in example :

`( ( ) ( ) ( ( ) ) )`
1 2  3  4 5  6  7  8  9  10

so here are all 10 steps:

steps  stack
1          (
2          (  (
3         (
4         (  (
5         (
6         (  (
7         (  (  (
8         (  (
9         (
10

Immediately it becomes clear that if the string  length is not an even number, it automatically becomes invalid. So we could do this check in the very beginning (lines 9 and 10)  below.

So let’s look at the current example where we have 3 different tags: ‘{}’, ‘()’, ‘[]’

The rule for a valid string is:
open tags:
– we could have as many open tag as we want. i.e. : `({[[ ...`
closing tags:
– every closing tag should match previously opened tag `([])` – valid, `([)]` – invalid.

So now we know the rules, let’s write the code.

```/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {

var input = s.split('');

if(input.length % 2 != 0)
return false;

var stack = [];

var tagIndex = {
'(': 0,
')': 1,
'{': 2,
'}': 3,
'[': 4,
']': 5
};

for(var q=0;q < input.length; q++) {
var symbol = input[q];
var tagType = (tagIndex[symbol] % 2); // 0 - open, 1 - close
if(tagType == 0) {
stack.push(symbol);
}
else {
// this is a closing tag, make sure that it follows the rules
lastTag = stack.pop();
lastTagIndex = tagIndex[lastTag];
if( tagIndex[symbol] != lastTagIndex + 1 )
return false;
}
}

if(stack.length > 0)
return false;
return true;
};```

what we just did:
– lines 9 and 10: we check if the length of the string is odd and return false immediately if so.
– we added tagIndex object where every bracket has it’s index which will help us to identify if we have the open or closing bracket.
– If it is open bracket, we just putting it inside the stack.
– if this is a close bracket, we are using the newly created  tagIndex to figure out if this is the right closing bracket from the same type. Simply following the rule that we described above (lines 32 -35)  `if( tagIndex[symbol] != lastTagIndex + 1 )` Basically we check if the previous opening tag in the stack is of the same type of the current closing tag.

# Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

This problem was taken from Leetcode

## Solution

Using a brute force we could merge the two arrays and find the median, but this is slow.
To optimize the solution we could use one of the properties of the arrays: the arrays are sorted.
– We could substitute the problem of find the median with find the numbers that are not in the median

The solution:

### Java Script

```/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {

function findMedianIndex(arr) {
var median = 0;
var i = 0;
if(arr.length % 2) {
var i = (arr.length / 2 + 0.5) - 1;
median = arr[i];
}
else {
var i = (arr.length / 2);
median = ((arr[i - 1] + arr[i]) / 2);
}
return median;
}

function isFirstArrayInTheMiddleOfSecondEvenArray(x, y) {
var minX = x[0];
var maxX = x [1];
var medianY = Math.floor(y.length / 2);
var leftMiddleY = y[medianY - 1];
var rightMiddleY = y[medianY];
return minX > leftMiddleY && maxX < rightMiddleY; } function findMedianOfArrayAndValue(arr, val) { if(arr.length == 0) { return val; } else if (typeof(val) == 'undefined') { return findMedianIndex(arr); } var median = 0; if(arr.length % 2) { // odd aray // var medianIndex = Math.floor((arr.length / 2)); // median = arr[medianIndex]; var arrMedian = findMedianIndex(arr); if(arrMedian > val) {
// the median of merged array should lie on the left of arr  <== var i = Math.floor(arr.length / 2); var right = arr[i]; var left = Math.max( arr[i - 1], val ); return findMedianIndex( [left, right] ); } else { // the median of merged array should lie on the right of arr ==>
var i = Math.floor(arr.length / 2);
var left = arr[i];
var right = Math.min( arr[i + 1], val );
return 	findMedianIndex( [left, right] );
}
}
else {
// even aray
var arrMedian = findMedianIndex(arr);
if(arrMedian > val) {
// the median of merged array should lie on the left of arr median  <== var i = Math.floor((arr.length / 2) - 1); var left = arr[i]; return Math.max(left, val); } else { // the median lies on the right side ==>
var i = (arr.length / 2);
var right = arr[i];
return Math.min(right, val);
}

median = findMedianIndex( [ arr[medianIndex], arr[medianIndex + 1] ]);

}
return ( Math.min(median, val) + Math.max(median, val) ) / 2;
}

function findMedian(X, Y) {

// check all odd cases
if (X.length === 1 && Y.length === 1) {
return (X[0] + Y[0]) / 2;
}

if(X.length <= 1) {
return findMedianOfArrayAndValue(Y, X[0]);
}
else if(Y.length <= 1) {
return findMedianOfArrayAndValue(X, Y[0]);
}
else if(X.length == 1 && Y.length == 1) {
var testArray = [ X[0], Y[0] ];
return findMedianIndex(testArray);
}
else if(X.length < 1) {
var testArray = Y.concat(X);
return findMedianIndex(testArray);
}
else if( Y.length < 1) { var testArray = X.concat(Y); return findMedianIndex(testArray); } if( X.length === 2 && Y.length >= 2 && Y.length % 2 === 0) {
if(isFirstArrayInTheMiddleOfSecondEvenArray(X, Y)) {
/*
in example:
var X = [1, 2];
var Y = [-1, 3];
*/
return (X[0] + X[1]) / 2;
}
}
if( Y.length === 2 && X.length >= 2 && X.length % 2 === 0) {
if(isFirstArrayInTheMiddleOfSecondEvenArray(Y, X)) {
/* and the other way */
return (Y[0] + Y[1]) / 2;
}
}

var mX = findMedianIndex(X);
var mY = findMedianIndex(Y);

if(mX == mY) {
return mX;
}

var splicePart = Math.floor(Math.min(X.length / 2 - 1, Y.length / 2 - 1));
splicePart = splicePart < 1 ? 1 : splicePart;

if (mX < mY) {
X.splice(0, splicePart);
Y.splice(Y.length - splicePart);
} else {
X.splice(X.length - splicePart);
Y.splice(0, splicePart);
}

return findMedian(X, Y);
}

return findMedian(nums1, nums2);
}
```

# Two Sum

#### Task: Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Examples :

```Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
```

This problem was taken from Leetcode

## One pass hash table.

Let’s take this example: nums = [2, 7, 11, 15], target = 9
The brute force solution might be to loop through each value in the nums array, and to add with each other value in the array and to compare with the target result.

### Optimize the algorithm using hash table

The idea is to store the array into a hash table where keys will be the values of the array (i.e: 2, 7, 11, 15) and the values: the element index (i.e: 0,1,2,3)
key:value
2 : 0,
7 : 1,
11:2,
15:3

This way all we need to do is:
– Iterate through the array once.
– For each value calculate what number could add to the target value ( x = target – nums[i])
– Dynamically add the next key-value pair into the hashmap

The solution:

## Java Script

```/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var hashMap = {};

for(var i in nums) {

var test = target - nums[i];
if(hashMap[test]) {
return [parseInt(hashMap[test]), parseInt(i)];
}
var key = nums[i];
hashMap[key] = i;
}
};

```

### C++

```class Solution {

public:
vector<int> twoSum(vector<int>& nums, int target) {

vector<int> result;

std::map<int, int> buffer;
for(int i = 0;i < nums.size(); i++) {
int key = nums[i];
int test = target - nums[i];

if(buffer[test] != 0) {
result = {buffer[test] -1, i};
break;
}
buffer[key] = i + 1;
}
return result;
}
};
```

# Longest Substring Without Repeating Characters

## 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

## 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 “ABCDECFGHlet’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:

1. 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.
2. 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;
}
};```