# 04.19.2022 - Algorithms/Extract digits of a number from both ends

Let's say, we have a problem that requires us to print all the digits of a number from the left to right.

A simple approach would be extracting the digits from the right to the left, storing them in an array, and printing that array in a reverse way.

$\underline{\normalsize{P}\small{RINT} \normalsize{D}\small{IGITS}\cdot\normalsize{R}\small{IGHT}\normalsize{T}\small{O}\normalsize{L}\small{EFT}(n)}$
$1: \quad digits \leftarrow \text{empty list}$
$2: \quad \textbf{while} \ n \gt 0$
$3: \quad \quad d \leftarrow n \ \text{mod} \ 10$
$4: \quad \quad n \leftarrow n \div 10$
$5: \quad \quad \textbf{push}\ d\ \rightarrow \ digits$
$6: \quad i := length\ of\ digits$
$7: \quad \textbf{while} \ i \geq 0$
$8: \quad \quad i \leftarrow i - 1$
$9: \quad \quad \textbf{print} \ digits[i]$

The time complexity of this algorithm would be $O(n)$, with $n$ being the number of digits in the input number. Since we need to allocate a new array, the algorithm would take $O(n)$ space as well.

To optimize the space complexity of the above algorithm, we can extract the digits from the left to the right. 

We can see that, for a number $n$ of $k$ digits, if we divide $n$ by $10^{k-1}$, the result is the first digit of $n$, for example, with $n = 54321$, there are $k = 5$ digits:

$$
54321 \div 10^4 = 5
$$

And the remainder of the above calculation is actually the number $n$ without its first digit!

$$
54321\ \text{mod} \ 10^4 = 4321
$$

We already know [how to count the digits of a number](/everyday/01-21-2022-math-count-number-of-digits-with-logarithm), it can be obtained by:

$$
k = log_{10}(n) + 1
$$

So, the algorithm to extract the digits from the left to the right would be:

$\underline{\normalsize{P}\small{RINT}\normalsize{D}\small{IGITS}\cdot\normalsize{L}\small{EFT}\normalsize{T}\small{O}\normalsize{R}\small{IGHT}(n)}$
$1: \quad k \leftarrow log_{10}(n) + 1$
$2: \quad \textbf{while} \ n \gt 0$
$3: \quad \quad d \leftarrow n \div 10^{k-1}$
$4: \quad \quad n \leftarrow n\ \text{mod} \ 10^{k-1}$
$5: \quad \quad k \leftarrow log_{10}(n) + 1$
$6: \quad \quad \textbf{print} \ d$

The new algorithm still has $O(n)$ time complexity, but this time, it only takes $O(1)$ space.

In line 5, we can also decrease $k$ by 1 instead of recalculating the number of digits with $log_{10}(n)$.

Extract digits of a number from both ends

# 04.18.2022 - Algorithms/Detect chess piece movement with Bitboard

In [the previous article](/everyday/04-17-2022-data-structures-introduction-to-bitboard), we learned about Bitboard and how to use it in a simple board game. In this article, let's see how Bitboard can be actually used to implement a chessboard.

---

For those who are never played chess, a chessboard is an 8x8 board, we people put one wooden piece on each cell and move them around to kill time. Sometimes, people get emotional and flip the board, sending the piece flying around then quickly escalate the situation into a fight. Just kidding.

![](_meta/chessboard.png)

To encode a chessboard on the computer, we usually define the board as a 2D matrix, with each cell being a string, they have one the value of `K (King)`, `Q (Queen)`, `P (Pawn)`, `B (Bishop)`, `N (Knight)`, `R (Rook)` to annotate which chess piece standing in it. Sometimes, people use uppercase letters for white pieces and lowercase letters for black pieces.

---

Another technique to represent the chessboard is using [Bitboard](https://pages.cs.wisc.edu/~psilord/blog/data/chess-pages/rep.html). It is a technique that uses multiple 64-bit numbers (instead of a 2D array) to maintain the position of each chess piece on the board, with 0 for the empty square and 1 for the current position of that piece on the board. You can read more about it in the reference link above, let's cut the explanation here and jump right into a real example.

Let's consider a smaller example of a 3x3 board, with a Pawn and a Knight. So we'll have 3 numbers to keep track of the pieces and the board:

![](_meta/bitboard-chess.png)

Now let's move the Knight from `b1` to `c3`, we have the new board data, how could we make sense of the new data and figure out which piece is moving, and move from which square, to which square?

![](_meta/bitboard-chess-move.png)

First, let's figure out the movement that just happens on the board, to do this, we apply the `XOR` operation between the old board and the new board.

Because there's only 1 moving piece each turn, the bits of every un-moved piece will remain the same on both boards, while the bits where the moving pieces go from and to will be changed. `XOR` operation will help us filter out all un-moved pieces:

![](_meta/bitboard-chess-xor-unmoved.png)

Now that we know what the movement looks like, we can go and ask every piece on the board if it's their move, by applying the `AND` operation to each of the piece.

If a piece is unmoved, none of its bits matched the bits in the movement value, so it would return 0. Otherwise, if a piece is moved, one of its bits will be matched with the bits in the movement value, the ultimate value would be some non-zero.

What if there are two pieces with the same zero return? The moving piece just landed on the square where there's already another piece, it's a capture!

Let's try it with the Pawn:

![](_meta/bitboard-pawn-move.png)

It's a zero, so the Pawn didn't move. How about the Knight?

![](_meta/bitboard-knight-move.png)

That looks like a non-zero to me, so the Knight just moved. In fact, it's the Knight's value itself. Look at the image above again, now, do you know how to calculate the Knight's new position?

Give yourself a pat on the back if you think of an `XOR`!

![](_meta/bitboard-knight-moved.png)

That's how we detect the movement and update the board. Let's summarize the algorithm:

1. **Step 1:** Calculate the movement value
   ```go
    movement = new_board XOR old_board 
    ```
2. **Step 2:** Find out what piece just moved, and calculate its new position
   ```go
    for each piece in [pieces]: 
        if movement AND piece == 0 then 
            piece = movement XOR piece
    ```

With this algorithm, we are now able to actually see the board movement from the software's perspective, based on the input data from the hardware, so we can actually implement some game rules like capture, illegal move checking, check or checkmate, en passant,...

Detect chess piece movement with Bitboard

# 04.10.2022 - Algorithms/Tracking letter frequency with Hashmap and Array

Sometimes, you will need to count the frequency of letters in a string and do something with that count.

For example, with a simple algorithm to check if a string is a permutation of another one, we can build a character frequency map of each string, and compare the two maps if they're the same.

$$\\begin{align}
s1 &= hello \\rightarrow \\{ h= 1, e= 1, l= 2, o= 1 \\} \\\\
s2 &= olleh \\rightarrow \\{ o= 1, l= 2, e= 1, h= 1 \\}
\\end{align}$$

There are different approaches for creating a character frequency map, like using a hashmap, or arrays.

A hashmap-alike data structure in JavaScript can be easily implemented using an empty object:

```javascript
const s = "hello";
const hash = {};

for (const i in s) {
    let chr = s[i];
    if (!hash[chr]) hash[chr] = 0;
    hash[chr]++;
}
```

You can pre-define the keys to avoid changing the shape of the hashmap on every loop. But for some small coding problems, it's not really a big deal.

Comparing the two hashmaps (or objects, in this case) is requires us to get all the keys in one map, and compare the value with its corresponding value in the other map:

```javascript
const compareTwoHashmaps = (hash, hash) => {
    for (const [chr, count] of Object.entries(hash)) {
        if (count !== hash[chr]) return false;
    }
    return true;
}
```

Another approach is to use an array as a map. We can use the fact that for each character, we can map their char code to the range from 0 by subtracting the char code with the char code of the letter **'a'**, or **97**.

```javascript
'a'.charCodeAt(0) - 'a'.charCodeAt(0) === 0
// or
'z'.charCodeAt(0) - 97 === 25
```

We can use this range number as an index in the frequency map array, assuming we only working with strings containing all lowercase letters:

```javascript
const s = "hello";
const hash = new Array(26).fill(0);

for (const i in s) {
    const chrCode = s[i].charCodeAt(0);
    hash[chrCode - 97]++;
}
```

$$
hash = \[ \\overset{a}{0}, \\overset{b}{0}, \\overset{c}{0}, \cdots, \\overset{e}{1},\cdots \\overset{h}{1},\cdots \\overset{l}{2},\cdots \\overset{o}{1},\cdots, \\overset{z}{0} \]
$$

To compare the two arrays, we just need to iterate and compare each position. Writing for loop is boring, in JavaScript, we make it more fun:

```javascript
hash1.every(i => hash2[i] === hash1[i])

// or

hash1.some(i => hash2[i] !== hash1[i])
```

But writing code like the two above examples might not great for code readability.

Speaking of readability, I really like that in Golang, it's more convenient to create the character frequency array.

```go
hash := [26]int{}

for i := range s {
    hash[s[i] - 'a']++
}
```

Since most coding problems will have well-defined constraints on the input string, it is more likely that the frequency hash will have a fixed size, like, all the letters from a to z, or a to Z. We can just use an array instead of slice.

Using arrays also have another benefit, we can compare two arrays directly without writing any for loop (of course, it's just about code readability, not talking about the complexity of the comparison here):

```go
if array1 == array2 {
    return true
}
```


Tracking letter frequency

# 04.08.2022 - Algorithms/Cyclic Sort: Sorting in O(N)

Cyclic Sort is an easy to implement and efficient algorithm. The only caveat is that it requires an input array to be a continuous range of values.

It can be applied to the problems of finding *duplicate* or *missing* numbers.

We can use the fact that the input values are a continuous range of numbers, every value will match its index somehow. For example, an array of **[0..10]** will have all its values matching its index. Or in an array of **[100..200]**, every value of index $i$ has the value of $i + 100$.

So, to tell if a value is in the correct position in the array, we can just check its index.

The way the cyclic sort algorithm works is, assuming the values are in the range of **[0..n]**:

1. **Step 1:** Create a **current** pointer, check for the number under the pointer **nums[current]**
2. **Step 2:** If **nums[current]** is in the correct position, increase the pointer to the next number
3. **Step 3:** If **nums[current]** is not in the correct position, move it to the correct position (**target = nums[current]**) and move the value that is occupying position **target** back to **current**.
4. **Step 4:** Repeat until **current** reaches the end of the array

Let's take an example, we want to sort the array **nums = [2, 4, 0, 6, 3, 5, 1]**. First, the **current** pointer is at index 0, which has a value of 2. This is not the correct value, so we move the value 2 to the index 2, swapping the value **nums[2] = 0** back to **nums[0]**.

![](_meta/cyclic-sort-01.png)

The value at **nums[current]** is now 0, which is correct. We can move the **current** pointer forward. This time, we have **current = 1**, the value at **nums[current] = 4**, which is not correct. So we move 4 into **nums[4]**, taking back the value at **nums[4]** and put it into **nums[1]**.

![](_meta/cyclic-sort-02.png)

Now, the value at **nums[current]** is 3, still not the correct value for its position, we cannot move the **current** pointer forward. Instead, let's swap 3 with the value at **nums[3]**:

![](_meta/cyclic-sort-03.png)

The value of **nums[current] = 6** still not the correct value for position **current = 1**, we have to swap one more time, this time, swap **nums[1]** with **nums[6]**:

![](_meta/cyclic-sort-04.png)

Now, at the position **current = 1**, the value **nums[current] = 1** is the correct value. We can move the **current** pointer forward.

![](_meta/cyclic-sort-05.png)

Since everything in the way are the correct values, we keep moving the pointer until we reach the end of the array, and the algorithm is finished.

The time complexity of the Cyclic Sort algorithm is $O(N)$. In the worst-case scenario, when we cannot increment the **current** pointer, it takes $O(2N - 1)$ time.

Here is the implementation of the Cyclic Sort algorithm:

```go
func CyclicSort(nums []int) {
	n := len(nums)
	i := 0
	for i < n {
		j := nums[i]
		if j < n && nums[j] != nums[i] {
			nums[j], nums[i] = nums[i], nums[j]
		} else {
			i++
		}
	}
}
```

For the problems that require us to find all the missing or duplicate numbers in an array, we can first sort the elements using Cyclic Sort and then loop through the sorted array to check if any value is displaced from its correct position.

```go
func findAllMissings(nums []int) []int {
	found := make([]int, 0)

	CyclicSort(nums)

	for i, n := range nums {
		if i != n {
			found = append(found, i)
		}
	}

	return found
}

func findAllDuplicates(nums []int) []int {
	found := make([]int, 0)

	CyclicSort(nums)

	for i, n := range nums {
		if i != n {
			found = append(found, n)
		}
	}

	return found
}
```

There is also a variant of Cyclic Sort that could return early when it finds the duplicate number during sorting, so we don't need a second loop:

```go
func findDuplicate(nums []int) int {
    n := len(nums)
    i := 0
    for i < n {
        if i != nums[i] {
            j := nums[i]
            if nums[j] != nums[i] {
                nums[j], nums[i] = nums[i], nums[j]
            } else {
                // Found the duplicate at i
                return i
            }
        } else {
            i++
        }
    }
    return -1
}
```


Cyclic Sort

# 04.07.2022 - Algorithms/Fast and Slow Pointers For Linked List

In a Linked List, traversal is restricted to forward only, you can't really go back to previous nodes once you go past them. When working on a problem that requires us to do some lookup in a Linked List, the naive approach is to traverse the list multiple times.

Another better approach is to use the *Fast and Slow Pointers* technique. Most of the time, we can solve the problem with a single pass.

Let's take a look at some example use cases.

## Find the $n^{th}$ node from the end of the list

Let's say, we want to find the $n^{th}$ node from the end of a Linked List, we can do it naively by traversing from the head to the tail to get the length $L$ of the list, then do a second traversal just $L - n$ times.

Using fast and slow pointers, we can first increase the **fast** pointer **n** times, the distance between **fast** and **slow** is now **n** nodes.

![](_meta/fast-slow-pointers-nth-node.png)

Now, increase both the **fast** and **slow** pointers until **fast** reaches the end of the list. Since the two pointers have the distance of **n**, the position of the **slow** pointer is the $n^{th}$ node from the end of the list.

![](_meta/fast-and-slow-pointers-first-example-final.png)

The algorithm can be implemented like this:

```go
fast := head
slow := head

for n > 0 {
    fast = fast.Next
}

for fast.Next != nil {
    fast = fast.Next
    slow = slow.Next
}

// slow is the nth from the end here
```

## Find the middle node of the list

Another example, this time we want to look for the middle node of the list. We can do it naively by traversal the list in two-pass, with the second pass in $L/2$ times.

Using fast and slow pointers, we increase the **slow** pointer one node at a time, and the **fast** pointer goes twice as fast with **fast = slow.Next.Next**, by the time **fast** reaches the end of the list, the **slow** pointer will be in the middle:

![](_meta/fast-and-slow-middle.png)

Implementation:

```go
fast := head
slow := head

for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}

// end of the loop, slow is the middle node
```

A similar technique can also be applied to detect a cycled linked list. Since the **fast** pointer will always, at some point, meet the **slow** pointer if it keeps cycling.

Fast and slow pointers for Linked List

# 04.03.2022 - Algorithms/Sliding Window With Two Pointers

For the problems that require us to do something a stream of values, or a subsequence of an array, the typical approach is to use a sliding window.

![](_meta/sliding-window.png)

A naive way to implement a sliding window is to have a nested loop, the first loop to iterate the start position of the window, and the second loop to collect the values inside a window:

```python
for(start = 0..array.length):
    for (end = start..start + window_length):
        // value array[start..end]
```

This algorithm would run in **O(N * K)** time, with **N** being the number of elements, and **K** is the window size.

A better approach to implementing sliding windows is to keep track of just the start and the end of the window. Since most of the items in between are overlapped when sliding, we can eliminate the inner loop, depending on what operation we need to perform on the array.

![](_meta/sliding-window-two-pointers.png)

For example, if a problem requires us to perform some work on the sum of each window, we can reuse the sum by adding the value of the new element and subtracting the value of the value at the beginning of the previous window.

```python
start = 0
sum = 0
for (end = 0..array.length):
	sum += array[end]
	sum -= array[start]
	start += 1
```

This approach only takes **O(N)** time.

Sometimes, you will need to check for all subarrays without the fixed window size, the windows could be shrinking or expanding depending on some conditions.

![](_meta/sliding-window-shrink.png)

In this case, the **start** and **end** pointers can be moved using this pattern:

```python
start = 0
for (end = 0..array.length):
	// do something
	...
	// shrink the window
	while (need_to_shrink):
		start += 1
```

The above approaches work well when you do not need to keep track of the overlapped items between the windows. In some problems, when working on a stream of data, you might need to have the information of all the items in between. In this case, using a circular buffer (or ring buffer) as a fixed queue would be a better solution.

![](_meta/sliding-window-circular-buffer.png)

A ring buffer can be easily implemented using an array for storing data, and two pointers for **writing** and **reading**.

![](_meta/sliding-window-circular-buffer-read-write.png)

Here's an implementation of a circular buffer using JavaScript:

```javascript
const CircularBuffer = function(size) {
    this.data = Array(size).fill(0).map(_ => 0);
    this.writePtr = 0;
    this.readPtr = 0;
    
    return {
        put: (value) => {
            this.data[this.writePtr++] = value;
            this.writePtr %= size;
        },
        get: () => {
            let item = this.data[this.readPtr++];
            this.readPtr %= size;
            return item;
        }
    }
};
```


Sliding Window

# 04.02.2022 - Algorithms/Merge two sorted arrays with extra space

**The problem**

Given two non-decreasing arrays `a` of length `m`, and `b` of length `n`. Merge the two arrays into array `a`. Since it’s an in-place merge, `a` has some extra spaces to fit the result.

**The solution**

Iterating from the end of both input arrays, at each iteration, pick the larger of the last two inputs and insert it into the end of the target array. Repeat this process until we reach the beginning of either input.

**For example:**

Given two arrays **a** and **b** of length **m** and **n** as follow:

$$ \\begin{align}
a &= [ 1, 3, 5, 0, 0, 0 ] &m = 3 \\\\
b &= [ 2, 4, 7 ] &n = 3 \\\\
\\end{align} $$

Let **k** be the last index of the merged array:

$$ k = m + n - 1 $$

Compare the two numbers $a[m-1]$ and $b[n-1]$ and insert the larger one into the end of the merged array (at position $a[k]$). After that, decrease the index $k$ and the value of $m$ or $n$ depending on which value is selected.

Repeat the process until either $m$ or $n$ reach the beginning of the array.

---

Here's how the algorithm running. From the beginning:

$$ \\begin{align}
a &= [ 1, 3, \\overset{\overset{m}\downarrow}{5}, 0, 0, \overset{\overset{k}\downarrow}{0} ] \\\\
b &= [ 2, 4, \underset{\underset{n}\uparrow}{7} ] \\\\
\\end{align} $$

We have $a[m] = 5$, which is smaller than $b[n] = 7$. Move $b[n]$ into the position $a[k]$, decrease the value of both $n$ and $k$ by 1:

$$ \\begin{align}
a &= [ 1, 3, \overset{\overset{m}\downarrow}{5}, 0,  \overset{\overset{k}\downarrow}{0}, 7 ] \\\\
b &= [ 2, \underset{\underset{n}\uparrow}{4}, \emptyset ] \\\\
\\end{align} $$

Now, $a[m] = 5$ is larger than $b[n] = 4$. Move $a[m]$ into $a[k]$ and decrease both $m$ and $k$ by 1:

$$ \\begin{align}
a &= [ 1, \overset{\overset{m}\downarrow}{3}, \emptyset,  \overset{\overset{k}\downarrow}{0}, 5, 7 ] \\\\
b &= [ 2, \underset{\underset{n}\uparrow}{4}, \emptyset ] \\\\
\\end{align} $$
Next, $a[m] = 3$, less than $b[n] = 4$. Move $b[n]$ into $a[k]$ and decrease both $n$ and $k$:

$$ \\begin{align}
a &= [ 1, \overset{\overset{m}\downarrow}{3},  \overset{\overset{k}\downarrow}{\emptyset}, 4, 5, 7 ] \\\\
b &= [ \underset{\underset{n}\uparrow}{2}, \emptyset, \emptyset ] \\\\
\\end{align} $$

Next, $a[m] = 3$, larger than $b[n] = 2$. Move $a[m]$ into $a[k]$ and decrease $m$ and $k$:

$$ \\begin{align}
a &= [ \overset{\overset{m}\downarrow}{1},  \overset{\overset{k}\downarrow}{\emptyset}, 3, 4, 5, 7 ] \\\\
b &= [ \underset{\underset{n}\uparrow}{2}, \emptyset, \emptyset ] \\\\
\\end{align} $$
Finally, move $b[n]$ into $a[k]$ since $a[m] = 1$ is less than $b[n] = 2$, decreasing $n$ and $k$:

$$ \\begin{align}
a &= [ \overset{\overset{m,k}\downarrow}{1}, 2, 3, 4, 5, 7 ] \\\\
b &= \underset{\underset{n}\uparrow}{[} \emptyset, \emptyset, \emptyset ] \\\\
\\end{align} $$

At this point, we reach the end of the algorithm, the merged result is:

$$ a = [1, 2, 3, 4, 5, 7] $$

Merge two sorted arrays with extra space

# 01.13.2022 - Algorithms/Comparing floating-point numbers

Due to rounding errors, most floating-point numbers cannot be represented precisely in the computer. This led to some weird situations like:

```javascript
0.1 + 0.2 = 0.30000000000000004
```

Different languages [handle this calculation differently](https://0.30000000000000004.com/).

So, we should not directly compare two floating-point numbers, but use the approximate approach, called epsilon comparison:

```
approxEqAbs(a, b) =
  diff := abs(a - b)
  return diff <= ε
```

Where ε is some acceptable error margin, often called _epsilon_ or _machine epsilon_. It's the distance between 1 and the next largest floating-point number, or `float(1 + ε) != 1`.

For example, for IEEE-754 single precision, ε = 2^-23:

```
            1 = 1.00000000000000000000000
1 + epsilon_m = 1.00000000000000000000001
                ^                       ^
               2^0                    2^(-23)
```

For double precision, ε = 2^-52:

```
            1 = 1.0000000000000000000000000000000000000000000000000000
1 + epsilon_m = 1.0000000000000000000000000000000000000000000000000001
                ^                                                    ^
               2^0                                                2^(-52)
```

It's predefined in many languages, for example:

-  `Number.EPSILON` in JavaScript/TypeScript
- `f16_epsilon`, `f32_epsilon`, `f64_epsilon`, `f128_epsilon` in Zig
- `FLT_EPSILON` in C++
- `f32::EPSILON`, `f64::EPSILON` in Rust

See [Values for standard hardware floating-point arithmetic](https://en.wikipedia.org/wiki/Machine_epsilon#Values_for_standard_hardware_floating_point_arithmetics) table on Wikipedia for more details.

The above approximation sounds right, but it only works for small numbers around zero. This won't work correctly for larger numbers because the gap between floats grows larger.

A better approach for this case is to use relative epsilon comparison: Calculate the absolute difference between the two numbers a and b, and if the difference is smaller than a fixed portion of the larger number, then a and b can be considered equal.

```
approxEqRelative(a, b) =
  largest := max(a, b)
  diff := abs(a - b)
  return diff <= largest * ε
```

In reality, when implementing these methods, we also need to pay attention to some edge cases. Such as, if `a` and `b` are zeros or infinities, we should just compare them directly with `==`, and if any of them is `NaN`, the comparison should just return `false`.

Following is the implementation of `approxEqAbs` and `approxEqRelative` in Zig's standard library:

**lib/std/math.zig**

```zig
pub fn approxEqAbs(comptime T: type, x: T, y: T, tolerance: T) bool {
    assert(@typeInfo(T) == .Float);
    assert(tolerance >= 0);

    // Fast path for equal values (and signed zeros and infinites).
    if (x == y)
        return true;

    if (isNan(x) or isNan(y))
        return false;

    return fabs(x - y) <= tolerance;
}

pub fn approxEqRel(comptime T: type, x: T, y: T, tolerance: T) bool {
    assert(@typeInfo(T) == .Float);
    assert(tolerance > 0);

    // Fast path for equal values (and signed zeros and infinites).
    if (x == y)
        return true;

    if (isNan(x) or isNan(y))
        return false;

    return fabs(x - y) <= max(fabs(x), fabs(y)) * tolerance;
}
```

**References:**

- https://courses.engr.illinois.edu/cs357/fa2019/references/ref-1-fp/
- https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
- https://floating-point-gui.de/errors/comparison/



Comparing floating-point numbers

# 12.27.2021 - Algorithms/Find Palindrome

When solving palindrome problems, we need to avoid sliding window solution (a.k.a brute force), where we try to generate every substring and check to find the palindrome.

The good approach to go for is the expandable solution.

For each character in the string, start expanding to the left and right of the character and check if each s[left] and s[right] pair are the same, if they're, expand the length of the palindrome string we found.

One thing we need to be aware of is, there are two cases of a palindrome:
- Odd length palindrome: which will be centered at a character, for example:
  ```
  abcba
    ^
  ```
- Even length palindrome: which will be centered in the middle of the two adjacent characters
  ```
  abba
   ^^
  ```

The algorithm to expand and find the palindrome is pretty easy to implement:

```
expand(s: string, l: int, r: int) -> int {
  while (l >= 0 && r < s.length() && s[l] == s[r]) {
    l--;
    r++;
  }
  return r - l - 1;
}
```

We use the `l` and `r` to mark the left and right boundary of the substring we want to check, if the pair are matched, we expand `l` to the left and `r` to the right until we reached the boundaries or the pair doesn't matched anymore.

Eventually, we return the length of the substring we found `r - l - 1`.

Now, whenever we want to check if a string is palindrome or not, we perform two check, one for the odd length palindrome, and another one for the even length palindrome:

Let's say we're at position #2, there are two strings we should check:

```
0 1 2 3 4 5
a b c c b d
    ^

   i = 2
 odd = expand(s, i, i) // centered at c
even = expand(s, i, i + 1) // centered between c and c
```

Given the length `len` of a palindrome substring, and the center of it, we can easily calculate the start and end point of that substring:

```
start = center - (len - 1) / 2;
end = center + len / 2;
```

Now that we have the algorithm to find palindrome centered at a character, here' the algorithm to find longest palindrome substring of a string:

```
int start = 0; int end = 0;
for (int i = 0; i < s.length(); i++) {
  int odd = expand(s, i, i);
  int even = expand(s, i, i + 1);
  int len = max(odd, even);
  if (len > end - start) {
    start = i - (len - 1) / 2;
    end = i + len / 2;
  }
}
return s.substr(start, end - start + 1);
```



Find Palindrome

# 12.26.2021 - Algorithms/Partition a number to sum of smaller ones

The array **x** is to keep track of all possible integers we can find, the array **t** is to keep the sum **t[i]** of every **x** number from **x[1]** to **x[i]**.

```javascript
const n = 8;
let x = [1];
let t = [0];

const gen = (i) => {
    for (let j = x[i - 1]; j <= ~~((n - t[i - 1]) / 2); j++) {
        x[i] = j;
        t[i] = t[i - 1] + j;
        gen(i + 1);
    }
    x[i] = n - t[i - 1];
    debug(x.slice(1, i+1));
};

gen(1);
```

Now, let's write a Generator algorithm with Backtracking.

Try every possible number from **1** to **n**, push them to an array **x** then check if it can sum up to **n** or not.

If it's not, pop it out from the array **x** and try a different one.

To make sure we don't have duplicate cases, we only select the result
array that are sorted.

```javascript
const n = 8;
let x = [];
let count = 0;

const sum = x => x.reduce((t, i) => t + i, 0);

const isSorted = (x) => {
    let clone = x.map(i => i);
    clone.sort((a,b) => a - b);
    for (let i = 0; i < x.length; i++) {
        if (x[i] !== clone[i]) return false;
    }
    return true;
};

const gen = i => {
    for (let j = 1; j <= n; j++) {
        x[i] = j;
        if (sum(x) === n) {
            if (isSorted(x)) {
                debug(x);
            }
            break;
        }
        if (i < n) {
            gen(i + 1);
        }
        x.pop();
    }
};

gen(0);
```



Partition a number to sum of smaller ones

# 12.25.2021 - Algorithms/Generate repeated combinatorial

The algorithm is simple:

 1. Find the right most element less than n
 2. Increase it
 3. Set the other right the same

It can be implemented as following:

```javascript
const next = (r) => {
    let n = r.length;
    for (let i = n - 1; i >= 0; i--) {
        if (r[i] < n) {
            r[i]++;
            for (let j = i; j < n; j++) {
                r[j] = r[i];
            }
            return r;
        }
    }
     return null;
};
```

And here's how we would use it:

```javascript
let gen = next([0, 0, 0, 0]);
while (gen != null) {
    console.log(gen);
    gen = next(gen);
}
```

