Count of Unique Triplets in a String

Given a string s consisting of lowercase English letters, find the number of consecutive triplets within s formed by unique characters. In other words, count the number of indices i, such that s[i], s[i + 1], and s[i + 2] are all pairwise distinct.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than
O(s.length²) will fit within the execution time limit.

Example

For s = "abcdaaae"the output should be solution(s) = 3

Explanation

• i = 0 → s[0] = 'a', s[1] = 'b', s[2] = 'c'
• i = 1 → s[1] = 'b', s[2] = 'c', s[3] = 'd'
• i = 2 → s[2] = 'c', s[3] = 'd', s[4] = 'a'
• i = 3 → s[3] = 'd', s[4] = 'a', s[5] = 'a'
• i = 4 → s[4] = 'a', s[5] = 'a', s[6] = 'a'
• i = 5 → s[5] = 'a', s[6] = 'a', s[7] = 'e'

For

s = "abacaba"

the output should be

solution(s) = 2

Explanation

Only two indices meet the criteria:

• i = 1: s[1] = 'b', s[2] = 'a', s[3] = 'c'
• i = 3: s[3] = 'c', s[4] = 'a', s[5] = 'b'

All other triplets contain one or more repeating characters.

Input/Output

[execution time limit] 4 seconds (py3)

[memory limit] 1 GB

[input] string s

A string consisting of lowercase English letters.

Guaranteed constraints:

1 ≤ s.length ≤ 1000

[output] integer

The number of indices i in s, such that characters s[i], s[i + 1], and s[i + 2] all exist and are pairwise distinct.

---

Subarrays Matching a Comparison Pattern

Given an array of integers numbers and an array pattern representing a comparison pattern, find how many subarrays of numbers match the given pattern.

pattern can only contain the following integers:

Pattern Definition

• pattern[i] = 1 — the number corresponding to this element of the pattern is greater than the previous one.
• pattern[i] = 0 — the number corresponding to this element of the pattern is equal to the previous one.
• pattern[i] = -1 — the number corresponding to this element of the pattern is less than the previous one.

It is guaranteed that numbers.length > pattern.length.

Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than
O(numbers.length × pattern.length) will fit within the execution time limit.

Example

For

numbers = [4, 1, 3, 4, 4, 5, 5, 1]
pattern = [1, 0, -1]

the output should be

solution(numbers, pattern) = 1

Explanation

Let's check all possible subarrays of length 3.
Note that the subarray [4, 1, 3], starting with numbers[0] = 4 does not need to be checked, as there is nothing to compare the first element with.

• Subarray [1, 3, 4] doesn't satisfy the pattern.
  pattern[0] = 1 means the first element of the subarray should be greater than the previous one,
  but numbers[1] = 1 < numbers[0] = 4.
• Subarray [3, 4, 4] doesn't satisfy the pattern.
  pattern[1] = 0 means the second element of the subarray should be equal to the previous one,
  but numbers[3] = 4 ≠ numbers[2] = 3.
• Subarray [4, 4, 5] doesn't satisfy the pattern.
  pattern[2] = -1 means the third element of the subarray should be less than the previous one,
  but numbers[5] = 5 > numbers[4] = 4.
• Following the same logic, subarray [4, 5, 5] doesn't satisfy the pattern.
• Subarray [5, 5, 1]satisfies the pattern, because:
  • numbers[5] > numbers[4] = 4 and pattern[0] = 1
  • numbers[5] == numbers[6] and pattern[1] = 0
  • numbers[7] < numbers[6] and pattern[2] = -1

Since there is a single subarray that satisfies the given pattern, the answer is 1.

Input/Output

[execution time limit] 4 seconds (py3)

[memory limit] 1 GB

[input] array.integer numbers

An array of integers.

Guaranteed constraints:

2 ≤ numbers.length ≤ 10⁴  
0 ≤ numbers[i] ≤ 10⁴

[input] array.integer pattern

An array of integers, containing only -1, 0, and 1.

Guaranteed constraints:

1 ≤ pattern.length < numbers.length  
-1 ≤ pattern[i] ≤ 1

[output] integer

The number of subarrays within the numbers that satisfies the given pattern.

---

Longest Diagonal Segment Matching Pattern

Given a matrix of integers, with each element containing either 0, 1, or 2, your task is to find the longest diagonal segment which matches the following pattern:
1, 2, 0, 2, 0, 2, 0, ...
(where the first element is 1, and then 2 and 0 are repeating infinitely), and finishes at a matrix border. Return the length of this diagonal segment.

The diagonal segment:

• May start at any matrix element
• May go toward any possible diagonal direction
• Must end at an element in the first or last row or column

Example

For

matrix = [[0, 0, 1, 2],
          [0, 2, 2, 2],
          [2, 1, 0, 1]]

the output should be

solution(matrix) = 3

For

matrix = [[2, 1, 2, 2, 0],
          [0, 0, 2, 0, 2],
          [0, 0, 0, 0, 0],
          [0, 0, 1, 2, 1],
          [2, 0, 0, 0, 1],
          [0, 2, 0, 0, 2]]

the output should be

solution(matrix) = 3

Explanation

Diagonal segment should start from an element containing 1, and there are three such elements in the given matrix. For each of these elements, try to go in all four diagonal directions until the pattern 1, 2, 0, 2, 0, ... breaks or a matrix border is reached. If any border was reached before the pattern breaks, update the best result (count of longest segment) if applicable.

There are three elements containing 1, so three possible starting points for diagonal segments. Try starting from all these elements one by one, and moving in all directions to find the longest possible diagonal segment which matches the pattern and ends at a matrix border.

Input/Output

[execution time limit] 4 seconds (py3)

[memory limit] 1 GB

[input] array.array.integer matrix

A matrix consisting of integers 0, 1, and/or 2.

---

2 × 2 Submatrices with Black Cells

Given a grid of black and white cells with rows rows and cols columns, you are given an array black that contains the [row, column] coordinates of all the black cells in the grid.

Your task is to compute how many 2 × 2 submatrices of the grid contain exactly blackCount black cells, for each 0 ≤ blackCount ≤ 4. As a result, you will return an array of 5 integers, where the ith element is the number of 2 × 2 submatrices with exactly i black cells.

It is guaranteed that black cell coordinates in the black array are pairwise unique, so the same cell is not colored twice.

Example

For

rows = 3
cols = 3
black = [[0, 0], [0, 1], [1, 0]]

the output should be

solution(rows, cols, black) = [1, 2, 0, 1, 0]

Explanation

• Initially, result = [0, 0, 0, 0, 0]
• The 2 × 2 submatrix with the upper-left corner at (0, 0) contains 3 black cells.
  result = [0, 0, 0, 1, 0]
• The 2 × 2 submatrix with the upper-left corner at (0, 1) contains 1 black cell.
  result = [0, 1, 0, 1, 0]
• The 2 × 2 submatrix with the upper-left corner at (1, 0) contains 1 black cell.
  result = [0, 2, 0, 1, 0]
• The 2 × 2 submatrix with the upper-left corner at (1, 1) contains 0 black cells.
  result = [1, 2, 0, 1, 0]

Input/Output

[execution time limit] 4 seconds (py3)

[memory limit] 1 GB

[input] integer rows

An integer representing the number of rows in the grid.

Guaranteed constraints:

2 ≤ rows ≤ 10⁵

[input] integer cols

An integer representing the number of columns in the grid.

Guaranteed constraints:

2 ≤ cols ≤ 10⁵

[input] array.array.integer black

An array of black cells. Each black cell is represented as a 2-element array [row, column]. Black cells are guaranteed to be all unique.

Guaranteed constraints:

0 ≤ black.length ≤ 500
black[i].length = 2
0 ≤ black[i][0] < rows
0 ≤ black[i][1] < cols

[output] array.integer64

An array of 5 integers, where the ith element is the number of 2 × 2 submatrices in the grid with i black cells.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.