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
Appearance settings

Commit 300c46d

Browse filesBrowse files
javadevjavadev
authored
Added tasks 3300-3307
1 parent d0a58d9 commit 300c46d
Copy full SHA for 300c46d

File tree

Expand file treeCollapse file tree

24 files changed

+941
-0
lines changed
Filter options
Expand file treeCollapse file tree

24 files changed

+941
-0
lines changed

‎src/main/kotlin/g3201_3300/s3300_minimum_element_after_replacement_with_digit_sum/Solution.kt

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package g3201_3300.s3300_minimum_element_after_replacement_with_digit_sum
2+
3+
// #Easy #Array #Math #2024_10_01_Time_153_ms_(100.00%)_Space_36.5_MB_(95.24%)
4+
5+
import kotlin.math.min
6+
7+
class Solution {
8+
fun minElement(nums: IntArray): Int {
9+
var min = Int.Companion.MAX_VALUE
10+
for (x in nums) {
11+
min = min(min, solve(x))
12+
}
13+
return min
14+
}
15+
16+
private fun solve(x: Int): Int {
17+
var x = x
18+
var sum = 0
19+
while (x != 0) {
20+
sum += x % 10
21+
x /= 10
22+
}
23+
return sum
24+
}
25+
}

‎src/main/kotlin/g3201_3300/s3300_minimum_element_after_replacement_with_digit_sum/readme.md

Copy file name to clipboard
+44Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3300\. Minimum Element After Replacement With Digit Sum
2+
3+
Easy
4+
5+
You are given an integer array `nums`.
6+
7+
You replace each element in `nums` with the **sum** of its digits.
8+
9+
Return the **minimum** element in `nums` after all replacements.
10+
11+
**Example 1:**
12+
13+
**Input:** nums = [10,12,13,14]
14+
15+
**Output:** 1
16+
17+
**Explanation:**
18+
19+
`nums` becomes `[1, 3, 4, 5]` after all replacements, with minimum element 1.
20+
21+
**Example 2:**
22+
23+
**Input:** nums = [1,2,3,4]
24+
25+
**Output:** 1
26+
27+
**Explanation:**
28+
29+
`nums` becomes `[1, 2, 3, 4]` after all replacements, with minimum element 1.
30+
31+
**Example 3:**
32+
33+
**Input:** nums = [999,19,199]
34+
35+
**Output:** 10
36+
37+
**Explanation:**
38+
39+
`nums` becomes `[27, 10, 19]` after all replacements, with minimum element 10.
40+
41+
**Constraints:**
42+
43+
* `1 <= nums.length <= 100`
44+
* <code>1 <= nums[i] <= 10<sup>4</sup></code>

‎src/main/kotlin/g3301_3400/s3301_maximize_the_total_height_of_unique_towers/Solution.kt

Copy file name to clipboard
+25Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package g3301_3400.s3301_maximize_the_total_height_of_unique_towers
2+
3+
// #Medium #Array #Sorting #Greedy #2024_10_01_Time_761_ms_(87.50%)_Space_68.1_MB_(77.50%)
4+
5+
class Solution {
6+
fun maximumTotalSum(maximumHeight: IntArray): Long {
7+
maximumHeight.sort()
8+
var result = maximumHeight[maximumHeight.size - 1].toLong()
9+
var previousHeight = maximumHeight[maximumHeight.size - 1].toLong()
10+
for (i in maximumHeight.size - 2 downTo 0) {
11+
if (previousHeight == 1L) {
12+
return -1
13+
}
14+
val height = maximumHeight[i].toLong()
15+
if (height >= previousHeight) {
16+
result = result + previousHeight - 1
17+
previousHeight = previousHeight - 1
18+
} else {
19+
result = result + height
20+
previousHeight = height
21+
}
22+
}
23+
return result
24+
}
25+
}

‎src/main/kotlin/g3301_3400/s3301_maximize_the_total_height_of_unique_towers/readme.md

Copy file name to clipboard
+47Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
3301\. Maximize the Total Height of Unique Towers
2+
3+
Medium
4+
5+
You are given an array `maximumHeight`, where `maximumHeight[i]` denotes the **maximum** height the <code>i<sup>th</sup></code> tower can be assigned.
6+
7+
Your task is to assign a height to each tower so that:
8+
9+
1. The height of the <code>i<sup>th</sup></code> tower is a positive integer and does not exceed `maximumHeight[i]`.
10+
2. No two towers have the same height.
11+
12+
Return the **maximum** possible total sum of the tower heights. If it's not possible to assign heights, return `-1`.
13+
14+
**Example 1:**
15+
16+
**Input:** maximumHeight = [2,3,4,3]
17+
18+
**Output:** 10
19+
20+
**Explanation:**
21+
22+
We can assign heights in the following way: `[1, 2, 4, 3]`.
23+
24+
**Example 2:**
25+
26+
**Input:** maximumHeight = [15,10]
27+
28+
**Output:** 25
29+
30+
**Explanation:**
31+
32+
We can assign heights in the following way: `[15, 10]`.
33+
34+
**Example 3:**
35+
36+
**Input:** maximumHeight = [2,2,1]
37+
38+
**Output:** \-1
39+
40+
**Explanation:**
41+
42+
It's impossible to assign positive heights to each index so that no two towers have the same height.
43+
44+
**Constraints:**
45+
46+
* <code>1 <= maximumHeight.length <= 10<sup>5</sup></code>
47+
* <code>1 <= maximumHeight[i] <= 10<sup>9</sup></code>

‎src/main/kotlin/g3301_3400/s3302_find_the_lexicographically_smallest_valid_sequence/Solution.kt

Copy file name to clipboard
+49Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package g3301_3400.s3302_find_the_lexicographically_smallest_valid_sequence
2+
3+
// #Medium #String #Dynamic_Programming #Greedy #Two_Pointers
4+
// #2024_10_01_Time_705_ms_(100.00%)_Space_65.9_MB_(100.00%)
5+
6+
class Solution {
7+
fun validSequence(word1: String, word2: String): IntArray? {
8+
val c1 = word1.toCharArray()
9+
val c2 = word2.toCharArray()
10+
val dp = IntArray(c1.size + 1)
11+
var j = c2.size - 1
12+
for (i in c1.indices.reversed()) {
13+
if (j >= 0 && c1[i] == c2[j]) {
14+
dp[i] = dp[i + 1] + 1
15+
j--
16+
} else {
17+
dp[i] = dp[i + 1]
18+
}
19+
}
20+
val ans = IntArray(c2.size)
21+
var i = 0
22+
j = 0
23+
while (i < c1.size && j < c2.size) {
24+
if (c1[i] == c2[j]) {
25+
ans[j] = i
26+
j++
27+
} else {
28+
if (dp[i + 1] >= c2.size - 1 - j) {
29+
ans[j] = i
30+
j++
31+
i++
32+
break
33+
}
34+
}
35+
i++
36+
}
37+
if (j < c2.size && i == c1.size) {
38+
return IntArray(0)
39+
}
40+
while (j < c2.size && i < c1.size) {
41+
if (c2[j] == c1[i]) {
42+
ans[j] = i
43+
j++
44+
}
45+
i++
46+
}
47+
return ans
48+
}
49+
}

‎src/main/kotlin/g3301_3400/s3302_find_the_lexicographically_smallest_valid_sequence/readme.md

Copy file name to clipboard
+65Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
3302\. Find the Lexicographically Smallest Valid Sequence
2+
3+
Medium
4+
5+
You are given two strings `word1` and `word2`.
6+
7+
A string `x` is called **almost equal** to `y` if you can change **at most** one character in `x` to make it _identical_ to `y`.
8+
9+
A sequence of indices `seq` is called **valid** if:
10+
11+
* The indices are sorted in **ascending** order.
12+
* _Concatenating_ the characters at these indices in `word1` in **the same** order results in a string that is **almost equal** to `word2`.
13+
14+
Return an array of size `word2.length` representing the lexicographically smallest **valid** sequence of indices. If no such sequence of indices exists, return an **empty** array.
15+
16+
**Note** that the answer must represent the _lexicographically smallest array_, **not** the corresponding string formed by those indices.
17+
18+
**Example 1:**
19+
20+
**Input:** word1 = "vbcca", word2 = "abc"
21+
22+
**Output:** [0,1,2]
23+
24+
**Explanation:**
25+
26+
The lexicographically smallest valid sequence of indices is `[0, 1, 2]`:
27+
28+
* Change `word1[0]` to `'a'`.
29+
* `word1[1]` is already `'b'`.
30+
* `word1[2]` is already `'c'`.
31+
32+
**Example 2:**
33+
34+
**Input:** word1 = "bacdc", word2 = "abc"
35+
36+
**Output:** [1,2,4]
37+
38+
**Explanation:**
39+
40+
The lexicographically smallest valid sequence of indices is `[1, 2, 4]`:
41+
42+
* `word1[1]` is already `'a'`.
43+
* Change `word1[2]` to `'b'`.
44+
* `word1[4]` is already `'c'`.
45+
46+
**Example 3:**
47+
48+
**Input:** word1 = "aaaaaa", word2 = "aaabc"
49+
50+
**Output:** []
51+
52+
**Explanation:**
53+
54+
There is no valid sequence of indices.
55+
56+
**Example 4:**
57+
58+
**Input:** word1 = "abc", word2 = "ab"
59+
60+
**Output:** [0,1]
61+
62+
**Constraints:**
63+
64+
* <code>1 <= word2.length < word1.length <= 3 * 10<sup>5</sup></code>
65+
* `word1` and `word2` consist only of lowercase English letters.

‎src/main/kotlin/g3301_3400/s3303_find_the_occurrence_of_first_almost_equal_substring/Solution.kt

Copy file name to clipboard
+60Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package g3301_3400.s3303_find_the_occurrence_of_first_almost_equal_substring
2+
3+
// #Hard #String #String_Matching #2024_10_01_Time_364_ms_(100.00%)_Space_40.8_MB_(100.00%)
4+
5+
import kotlin.math.abs
6+
7+
class Solution {
8+
fun minStartingIndex(s: String, pattern: String): Int {
9+
val n = s.length
10+
var left = 0
11+
var right = 0
12+
val f1 = IntArray(26)
13+
val f2 = IntArray(26)
14+
for (ch in pattern.toCharArray()) {
15+
f2[ch.code - 'a'.code]++
16+
}
17+
while (right < n) {
18+
val ch = s[right]
19+
f1[ch.code - 'a'.code]++
20+
if (right - left + 1 == pattern.length + 1) {
21+
f1[s[left].code - 'a'.code]--
22+
left += 1
23+
}
24+
if (right - left + 1 == pattern.length && check(f1, f2, left, s, pattern)) {
25+
return left
26+
}
27+
right += 1
28+
}
29+
return -1
30+
}
31+
32+
private fun check(f1: IntArray, f2: IntArray, left: Int, s: String, pattern: String): Boolean {
33+
var cnt = 0
34+
for (i in 0..25) {
35+
if (f1[i] != f2[i]) {
36+
if ((abs((f1[i] - f2[i])) > 1) || (abs(f1[i] - f2[i]) != 1 && cnt == 2)) {
37+
return false
38+
}
39+
cnt += 1
40+
}
41+
}
42+
cnt = 0
43+
var start = 0
44+
var end = pattern.length - 1
45+
while (start <= end) {
46+
if (s[start + left] != pattern[start]) {
47+
cnt += 1
48+
}
49+
if (start + left != left + end && s[left + end] != pattern[end]) {
50+
cnt += 1
51+
}
52+
if (cnt >= 2) {
53+
return false
54+
}
55+
start++
56+
end--
57+
}
58+
return true
59+
}
60+
}

‎src/main/kotlin/g3301_3400/s3303_find_the_occurrence_of_first_almost_equal_substring/readme.md

Copy file name to clipboard
+50Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
3303\. Find the Occurrence of First Almost Equal Substring
2+
3+
Hard
4+
5+
You are given two strings `s` and `pattern`.
6+
7+
A string `x` is called **almost equal** to `y` if you can change **at most** one character in `x` to make it _identical_ to `y`.
8+
9+
Return the **smallest** _starting index_ of a substring in `s` that is **almost equal** to `pattern`. If no such index exists, return `-1`.
10+
11+
A **substring** is a contiguous **non-empty** sequence of characters within a string.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "abcdefg", pattern = "bcdffg"
16+
17+
**Output:** 1
18+
19+
**Explanation:**
20+
21+
The substring `s[1..6] == "bcdefg"` can be converted to `"bcdffg"` by changing `s[4]` to `"f"`.
22+
23+
**Example 2:**
24+
25+
**Input:** s = "ababbababa", pattern = "bacaba"
26+
27+
**Output:** 4
28+
29+
**Explanation:**
30+
31+
The substring `s[4..9] == "bababa"` can be converted to `"bacaba"` by changing `s[6]` to `"c"`.
32+
33+
**Example 3:**
34+
35+
**Input:** s = "abcd", pattern = "dba"
36+
37+
**Output:** \-1
38+
39+
**Example 4:**
40+
41+
**Input:** s = "dde", pattern = "d"
42+
43+
**Output:** 0
44+
45+
**Constraints:**
46+
47+
* <code>1 <= pattern.length < s.length <= 3 * 10<sup>5</sup></code>
48+
* `s` and `pattern` consist only of lowercase English letters.
49+
50+
**Follow-up:** Could you solve the problem if **at most** `k` **consecutive** characters can be changed?

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.