- Difficulty: Medium.

- Related Topics: Hash Table, String, Bit Manipulation, Sliding Window, Rolling Hash, Hash Function.

- Similar Questions: .

The **DNA sequence** is composed of a series of nucleotides abbreviated as `'A'`, `'C'`, `'G'`, and `'T'`.

- For example, `"ACGAATTCCG"` is a **DNA sequence**.

When studying **DNA**, it is useful to identify repeated sequences within the DNA.

Given a string `s` that represents a **DNA sequence**, return all the **`10`-letter-long** sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in **any order**.

 

Example 1:

Input: s = "AAAAAAAAAAAAA"

Output: ["AAAAAAAAAA"]

**Explain:**

nope.

**Complexity:**

* Time complexity : O(n).

* Space complexity : O(1).

- Difficulty: Easy.

- Related Topics: Divide and Conquer, Bit Manipulation.

- Similar Questions: Reverse Bits, Power of Two, Counting Bits, Binary Watch, Hamming Distance, Binary Number with Alternating Bits, Prime Number of Set Bits in Binary Representation.

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

**Note:**

- Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. `-3`.

 

Example 1:

Example 2:

Example 3:

 

**Constraints:**

- The input must be a **binary string** of length `32`.

 

**Follow up:** If this function is called many times, how would you optimize it?

var hammingWeight = function(n) {

var count = 0;

while (n) {

if (n & 1) count++;

n >>>= 1;

}

return count;

};

**Explain:**

use `>>>` instead of `>>`.

**Complexity:**

* Time complexity : O(1).

* Space complexity : O(1).

- Difficulty: Easy.

- Related Topics: Array, Hash Table, String.

- Similar Questions: Rearrange Characters to Make Target String.

You are given an array of strings `words` and a string `chars`.

A string is **good** if it can be formed by characters from chars (each character can only be used once).

Return **the sum of lengths of all good strings in words**.

 

Example 1:

Example 2:

 

**Constraints:**

- `1 <= words.length <= 1000`

- `1 <= words[i].length, chars.length <= 100`

- `words[i]` and `chars` consist of lowercase English letters.

var countCharacters = function(words, chars) {

var map = Array(26).fill(0);

var a = 'a'.charCodeAt(0);

for (var i = 0; i < chars.length; i++) {

map[chars.charCodeAt(i) - a]++;

}

var res = 0;

outerLoop: for (var m = 0; m < words.length; m++) {

var arr = Array.from(map);

for (var n = 0; n < words[m].length; n++) {

if (--arr[words[m].charCodeAt(n) - a] < 0) continue outerLoop;

}

res += words[m].length;

}

return res;

};

**Explain:**

nope.

**Complexity:**

* Time complexity : O(m * n).

* Space complexity : O(1).

- Difficulty: Hard.

- Related Topics: Union Find, Graph, Sorting, Minimum Spanning Tree, Strongly Connected Component.

- Similar Questions: .

Given a weighted undirected connected graph with `n` vertices numbered from `0` to `n - 1`, and an array `edges` where `edges[i] = [ai, bi, weighti]` represents a bidirectional and weighted edge between nodes `ai` and `bi`. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.

Find **all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST)**. An MST edge whose deletion from the graph would cause the MST weight to increase is called a **critical edge**. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

 

Example 1:

Example 2:

 

**Constraints:**

- `2 <= n <= 100`

- `1 <= edges.length <= min(200, n * (n - 1) / 2)`

- `edges[i].length == 3`

- `0 <= ai < bi < n`

- `1 <= weighti <= 1000`

- All pairs `(ai, bi)` are **distinct**.

var findCriticalAndPseudoCriticalEdges = function(n, edges) {

var [min] = findMinSpanningTreeWeight(n, edges);

var res = [[], []];

for (var i = 0; i < edges.length; i++) {

var [num, parents] = findMinSpanningTreeWeight(n, edges, undefined, edges[i]);

var root = find(parents, 0);

var isCritical = num > min || !Array(n).fill(0).every((_, k) => find(parents, k) === root);

if (isCritical) {

res[0].push(i);

} else {

var [num2] = findMinSpanningTreeWeight(n, edges, edges[i], undefined);

if (num2 === min) res[1].push(i);

}

}

return res;

};

var findMinSpanningTreeWeight = function(n, edges, mustHaveItem, mustNotHaveItem) {

edges = [...edges];

edges.sort((a, b) => a[2] - b[2]);

if (mustHaveItem !== undefined) {

edges = edges.filter((item) => item !== mustHaveItem);

edges.unshift(mustHaveItem);

}

var res = 0;

var parents = Array(n).fill(0).map((_, i) => i);

var count = Array(n).fill(0);

for (var i = 0; i < edges.length; i++) {

if (edges[i] === mustNotHaveItem) continue;

var [m, k, distance] = edges[i];

var j = find(parents, m);

var p = find(parents, k);

if (j === p) continue;

if (count[j] <= count[p]) {

union(parents, j, p);

count[p]++;

} else {

union(parents, p, j);

count[j]++;

}

res += distance;

}

return [res, parents];

};

var find = function(parents, i) {

if (parents[i] === i) return i

parents[i] = find(parents, parents[i]);

return parents[i];

};

var union = function(parents, i, j) {

parents[i] = j;

};

**Explain:**

nope.

**Complexity:**

* Time complexity : O(m * n ^ 2).

* Space complexity : O(n ^ 2).