Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 3f1908f

Browse files
authored
Added tasks 3692-3700
1 parent e2b5b52 commit 3f1908f

File tree

24 files changed

+1228
-0
lines changed

24 files changed

+1228
-0
lines changed
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package g3601_3700.s3692_majority_frequency_characters
2+
3+
// #Easy #Biweekly_Contest_166 #2025_10_03_Time_2_ms_(100.00%)_Space_43.05_MB_(100.00%)
4+
5+
class Solution {
6+
fun majorityFrequencyGroup(s: String): String {
7+
val cntArray = IntArray(26)
8+
for (i in 0..<s.length) {
9+
cntArray[s[i].code - 'a'.code]++
10+
}
11+
val freq = IntArray(s.length + 1)
12+
for (i in 0..25) {
13+
if (cntArray[i] > 0) {
14+
freq[cntArray[i]]++
15+
}
16+
}
17+
var size = 0
18+
var bfreq = 0
19+
for (i in 0..s.length) {
20+
val si = freq[i]
21+
if (si > size || (si == size && i > bfreq)) {
22+
size = si
23+
bfreq = i
24+
}
25+
}
26+
val sb = StringBuilder()
27+
for (i in 0..25) {
28+
if (cntArray[i] == bfreq) {
29+
sb.append((i + 'a'.code).toChar())
30+
}
31+
}
32+
return sb.toString()
33+
}
34+
}
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
3692\. Majority Frequency Characters
2+
3+
Easy
4+
5+
You are given a string `s` consisting of lowercase English letters.
6+
7+
The **frequency group** for a value `k` is the set of characters that appear exactly `k` times in s.
8+
9+
The **majority frequency group** is the frequency group that contains the largest number of **distinct** characters.
10+
11+
Return a string containing all characters in the majority frequency group, in **any** order. If two or more frequency groups tie for that largest size, pick the group whose frequency `k` is **larger**.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "aaabbbccdddde"
16+
17+
**Output:** "ab"
18+
19+
**Explanation:**
20+
21+
| Frequency (k) | Distinct characters in group | Group size | Majority? |
22+
|---------------|------------------------------|------------|-----------|
23+
| 4 | {d} | 1 | No |
24+
| 3 | {a, b} | 2 | **Yes** |
25+
| 2 | {c} | 1 | No |
26+
| 1 | {e} | 1 | No |
27+
28+
Both characters `'a'` and `'b'` share the same frequency 3, they are in the majority frequency group. `"ba"` is also a valid answer.
29+
30+
**Example 2:**
31+
32+
**Input:** s = "abcd"
33+
34+
**Output:** "abcd"
35+
36+
**Explanation:**
37+
38+
| Frequency (k) | Distinct characters in group | Group size | Majority? |
39+
|---------------|------------------------------|------------|-----------|
40+
| 1 | {a, b, c, d} | 4 | **Yes** |
41+
42+
All characters share the same frequency 1, they are all in the majority frequency group.
43+
44+
**Example 3:**
45+
46+
**Input:** s = "pfpfgi"
47+
48+
**Output:** "fp"
49+
50+
**Explanation:**
51+
52+
| Frequency (k) | Distinct characters in group | Group size | Majority? |
53+
|---------------|------------------------------|------------|----------------------------------|
54+
| 2 | {p, f} | 2 | **Yes** |
55+
| 1 | {g, i} | 2 | No (tied size, lower frequency) |
56+
57+
Both characters `'p'` and `'f'` share the same frequency 2, they are in the majority frequency group. There is a tie in group size with frequency 1, but we pick the higher frequency: 2.
58+
59+
**Constraints:**
60+
61+
* `1 <= s.length <= 100`
62+
* `s` consists only of lowercase English letters.
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package g3601_3700.s3693_climbing_stairs_ii
2+
3+
// #Medium #Biweekly_Contest_166 #2025_10_03_Time_8_ms_(100.00%)_Space_80.61_MB_(12.90%)
4+
5+
import kotlin.math.min
6+
7+
@Suppress("unused")
8+
class Solution {
9+
fun climbStairs(n: Int, costs: IntArray): Int {
10+
if (costs.size == 1) {
11+
return costs[0] + 1
12+
}
13+
var one = costs[0] + 1
14+
var two = min(one + costs[1] + 1, costs[1] + 4)
15+
if (costs.size < 3) {
16+
return two
17+
}
18+
var three = min(one + costs[2] + 4, min(two + costs[2] + 1, costs[2] + 9))
19+
if (costs.size < 4) {
20+
return three
21+
}
22+
for (i in 3..<costs.size) {
23+
val four =
24+
(
25+
min(
26+
three + costs[i] + 1,
27+
min(two + costs[i] + 4, one + costs[i] + 9),
28+
)
29+
)
30+
one = two
31+
two = three
32+
three = four
33+
}
34+
return three
35+
}
36+
}
Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
3693\. Climbing Stairs II
2+
3+
Medium
4+
5+
You are climbing a staircase with `n + 1` steps, numbered from 0 to `n`.
6+
7+
You are also given a **1-indexed** integer array `costs` of length `n`, where `costs[i]` is the cost of step `i`.
8+
9+
From step `i`, you can jump **only** to step `i + 1`, `i + 2`, or `i + 3`. The cost of jumping from step `i` to step `j` is defined as: <code>costs[j] + (j - i)<sup>2</sup></code>
10+
11+
You start from step 0 with `cost = 0`.
12+
13+
Return the **minimum** total cost to reach step `n`.
14+
15+
**Example 1:**
16+
17+
**Input:** n = 4, costs = [1,2,3,4]
18+
19+
**Output:** 13
20+
21+
**Explanation:**
22+
23+
One optimal path is `0 → 1 → 2 → 4`
24+
25+
Jump
26+
27+
Cost Calculation
28+
29+
Cost
30+
31+
0 → 1
32+
33+
<code>costs[1] + (1 - 0)<sup>2</sup> = 1 + 1</code>
34+
35+
2
36+
37+
1 → 2
38+
39+
<code>costs[2] + (2 - 1)<sup>2</sup> = 2 + 1</code>
40+
41+
3
42+
43+
2 → 4
44+
45+
<code>costs[4] + (4 - 2)<sup>2</sup> = 4 + 4</code>
46+
47+
8
48+
49+
Thus, the minimum total cost is `2 + 3 + 8 = 13`
50+
51+
**Example 2:**
52+
53+
**Input:** n = 4, costs = [5,1,6,2]
54+
55+
**Output:** 11
56+
57+
**Explanation:**
58+
59+
One optimal path is `0 → 2 → 4`
60+
61+
Jump
62+
63+
Cost Calculation
64+
65+
Cost
66+
67+
0 → 2
68+
69+
<code>costs[2] + (2 - 0)<sup>2</sup> = 1 + 4</code>
70+
71+
5
72+
73+
2 → 4
74+
75+
<code>costs[4] + (4 - 2)<sup>2</sup> = 2 + 4</code>
76+
77+
6
78+
79+
Thus, the minimum total cost is `5 + 6 = 11`
80+
81+
**Example 3:**
82+
83+
**Input:** n = 3, costs = [9,8,3]
84+
85+
**Output:** 12
86+
87+
**Explanation:**
88+
89+
The optimal path is `0 → 3` with total cost = <code>costs[3] + (3 - 0)<sup>2</sup> = 3 + 9 = 12</code>
90+
91+
**Constraints:**
92+
93+
* <code>1 <= n == costs.length <= 10<sup>5</sup></code>
94+
* <code>1 <= costs[i] <= 10<sup>4</sup></code>
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package g3601_3700.s3694_distinct_points_reachable_after_substring_removal
2+
3+
// #Medium #Biweekly_Contest_166 #2025_10_03_Time_46_ms_(100.00%)_Space_48.62_MB_(100.00%)
4+
5+
class Solution {
6+
fun distinctPoints(s: String, k: Int): Int {
7+
val seen: MutableSet<Long> = HashSet()
8+
seen.add(0L)
9+
var x = 0
10+
var y = 0
11+
for (i in k..<s.length) {
12+
// add new step
13+
when (s[i]) {
14+
'U' -> y++
15+
'D' -> y--
16+
'L' -> x++
17+
'R' -> x--
18+
else -> x--
19+
}
20+
// remove old step
21+
when (s[i - k]) {
22+
'U' -> y--
23+
'D' -> y++
24+
'L' -> x--
25+
'R' -> x++
26+
else -> x++
27+
}
28+
seen.add(1000000L * x + y)
29+
}
30+
return seen.size
31+
}
32+
}
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
3694\. Distinct Points Reachable After Substring Removal
2+
3+
Medium
4+
5+
You are given a string `s` consisting of characters `'U'`, `'D'`, `'L'`, and `'R'`, representing moves on an infinite 2D Cartesian grid.
6+
7+
* `'U'`: Move from `(x, y)` to `(x, y + 1)`.
8+
* `'D'`: Move from `(x, y)` to `(x, y - 1)`.
9+
* `'L'`: Move from `(x, y)` to `(x - 1, y)`.
10+
* `'R'`: Move from `(x, y)` to `(x + 1, y)`.
11+
12+
You are also given a positive integer `k`.
13+
14+
You **must** choose and remove **exactly one** contiguous substring of length `k` from `s`. Then, start from coordinate `(0, 0)` and perform the remaining moves in order.
15+
16+
Return an integer denoting the number of **distinct** final coordinates reachable.
17+
18+
**Example 1:**
19+
20+
**Input:** s = "LUL", k = 1
21+
22+
**Output:** 2
23+
24+
**Explanation:**
25+
26+
After removing a substring of length 1, `s` can be `"UL"`, `"LL"` or `"LU"`. Following these moves, the final coordinates will be `(-1, 1)`, `(-2, 0)` and `(-1, 1)` respectively. There are two distinct points `(-1, 1)` and `(-2, 0)` so the answer is 2.
27+
28+
**Example 2:**
29+
30+
**Input:** s = "UDLR", k = 4
31+
32+
**Output:** 1
33+
34+
**Explanation:**
35+
36+
After removing a substring of length 4, `s` can only be the empty string. The final coordinates will be `(0, 0)`. There is only one distinct point `(0, 0)` so the answer is 1.
37+
38+
**Example 3:**
39+
40+
**Input:** s = "UU", k = 1
41+
42+
**Output:** 1
43+
44+
**Explanation:**
45+
46+
After removing a substring of length 1, `s` becomes `"U"`, which always ends at `(0, 1)`, so there is only one distinct final coordinate.
47+
48+
**Constraints:**
49+
50+
* <code>1 <= s.length <= 10<sup>5</sup></code>
51+
* `s` consists of only `'U'`, `'D'`, `'L'`, and `'R'`.
52+
* `1 <= k <= s.length`
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package g3601_3700.s3695_maximize_alternating_sum_using_swaps
2+
3+
// #Hard #Biweekly_Contest_166 #2025_10_03_Time_61_ms_(100.00%)_Space_105.29_MB_(100.00%)
4+
5+
class Solution {
6+
private lateinit var root: IntArray
7+
8+
fun maxAlternatingSum(nums: IntArray, swaps: Array<IntArray>): Long {
9+
val n = nums.size
10+
root = IntArray(n) { it }
11+
val list = Array(n) { ArrayList<Int>() }
12+
val oddCount = IntArray(n)
13+
for (s in swaps) {
14+
union(s[0], s[1])
15+
}
16+
for (i in nums.indices) {
17+
val r = findRoot(i)
18+
list[r].add(nums[i])
19+
if (i % 2 == 1) {
20+
oddCount[r]++
21+
}
22+
}
23+
24+
var result = 0L
25+
for (i in 0 until n) {
26+
if (root[i] != i) {
27+
continue
28+
}
29+
val currentList = list[i]
30+
val currentOddCount = oddCount[i]
31+
currentList.sort()
32+
for (j in currentList.indices) {
33+
val value = currentList[j].toLong()
34+
val multiplier = if (j < currentOddCount) -1 else 1
35+
result += value * multiplier
36+
}
37+
}
38+
return result
39+
}
40+
41+
private fun union(a: Int, b: Int) {
42+
val rootA = findRoot(a)
43+
val rootB = findRoot(b)
44+
if (rootA != rootB) {
45+
if (rootA < rootB) {
46+
root[rootB] = rootA
47+
} else {
48+
root[rootA] = rootB
49+
}
50+
}
51+
}
52+
53+
private fun findRoot(a: Int): Int {
54+
if (a == root[a]) {
55+
return a
56+
}
57+
return findRoot(root[a]).also { root[a] = it }
58+
}
59+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /