Movatterモバイル変換

[0]ホーム
URL:

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

Added tasks 3597-3600#2003

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
javadev merged 5 commits intojavadev:mainfromjscrdev:tasks-3597-3600
Jun 30, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
35 changes: 35 additions & 0 deletionssrc/main/java/g3501_3600/s3597_partition_string/Solution.java
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
package g3501_3600.s3597_partition_string;

// #Medium #String #Hash_Table #Simulation #Trie
// #2025_06_30_Time_25_ms_(100.00%)_Space_55.91_MB_(100.00%)

import java.util.ArrayList;
import java.util.List;

public class Solution {
private static class Trie {
Trie[] tries = new Trie[26];
}

public List<String> partitionString(String s) {
Trie trie = new Trie();
List<String> res = new ArrayList<>();
Trie node = trie;
int i = 0;
int j = 0;
while (i < s.length() && j < s.length()) {
int idx = s.charAt(j) - 'a';
if (node.tries[idx] == null) {
res.add(s.substring(i, j + 1));
node.tries[idx] = new Trie();
i = j + 1;
j = i;
node = trie;
} else {
node = node.tries[idx];
j++;
}
}
return res;
}
}
59 changes: 59 additions & 0 deletionssrc/main/java/g3501_3600/s3597_partition_string/readme.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
3597\. Partition String

Medium

Given a string`s`, partition it into**unique segments** according to the following procedure:

* Start building a segment beginning at index 0.
* Continue extending the current segment character by character until the current segment has not been seen before.
* Once the segment is unique, add it to your list of segments, mark it as seen, and begin a new segment from the next index.
* Repeat until you reach the end of`s`.

Return an array of strings`segments`, where`segments[i]` is the <code>i<sup>th</sup></code> segment created.

**Example 1:**

**Input:** s = "abbccccd"

**Output:**["a","b","bc","c","cc","d"]

**Explanation:**

Here is your table, converted from HTML to Markdown:

| Index| Segment After Adding| Seen Segments| Current Segment Seen Before?| New Segment| Updated Seen Segments|
|-------|----------------------|-----------------------|------------------------------|-------------|----------------------------------|
| 0| "a"|[]| No| ""|["a"]|
| 1| "b"|["a"]| No| ""|["a", "b"]|
| 2| "b"|["a", "b"]| Yes| "b"|["a", "b"]|
| 3| "bc"|["a", "b"]| No| ""|["a", "b", "bc"]|
| 4| "c"|["a", "b", "bc"]| No| ""|["a", "b", "bc", "c"]|
| 5| "c"|["a", "b", "bc", "c"]| Yes| "c"|["a", "b", "bc", "c"]|
| 6| "cc"|["a", "b", "bc", "c"]| No| ""|["a", "b", "bc", "c", "cc"]|
| 7| "d"|["a", "b", "bc", "c", "cc"]| No| ""|["a", "b", "bc", "c", "cc", "d"]|

Hence, the final output is`["a", "b", "bc", "c", "cc", "d"]`.

**Example 2:**

**Input:** s = "aaaa"

**Output:**["a","aa"]

**Explanation:**

Here is your table converted to Markdown:

| Index| Segment After Adding| Seen Segments| Current Segment Seen Before?| New Segment| Updated Seen Segments|
|-------|----------------------|---------------|------------------------------|-------------|----------------------|
| 0| "a"|[]| No| ""|["a"]|
| 1| "a"|["a"]| Yes| "a"|["a"]|
| 2| "aa"|["a"]| No| ""|["a", "aa"]|
| 3| "a"|["a", "aa"]| Yes| "a"|["a", "aa"]|

Hence, the final output is`["a", "aa"]`.

**Constraints:**

* <code>1 <= s.length <= 10<sup>5</sup></code>
*`s` contains only lowercase English letters.
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
package g3501_3600.s3598_longest_common_prefix_between_adjacent_strings_after_removals;

// #Medium #Array #String #2025_06_30_Time_28_ms_(74.57%)_Space_67.08_MB_(39.11%)

public class Solution {
private int solve(String a, String b) {
int len = Math.min(a.length(), b.length());
int cnt = 0;
while (cnt < len && a.charAt(cnt) == b.charAt(cnt)) {
cnt++;
}
return cnt;
}

public int[] longestCommonPrefix(String[] words) {
int n = words.length;
int[] ans = new int[n];
if (n <= 1) {
return ans;
}
int[] lcp = new int[n - 1];
for (int i = 0; i + 1 < n; i++) {
lcp[i] = solve(words[i], words[i + 1]);
}
int[] prefmax = new int[n - 1];
int[] sufmax = new int[n - 1];
prefmax[0] = lcp[0];
for (int i = 1; i < n - 1; i++) {
prefmax[i] = Math.max(prefmax[i - 1], lcp[i]);
}
sufmax[n - 2] = lcp[n - 2];
for (int i = n - 3; i >= 0; i--) {
sufmax[i] = Math.max(sufmax[i + 1], lcp[i]);
}
for (int i = 0; i < n; i++) {
int best = 0;
if (i >= 2) {
best = Math.max(best, prefmax[i - 2]);
}
if (i + 1 <= n - 2) {
best = Math.max(best, sufmax[i + 1]);
}
if (i > 0 && i < n - 1) {
best = Math.max(best, solve(words[i - 1], words[i + 1]));
}
ans[i] = best;
}
return ans;
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
3598\. Longest Common Prefix Between Adjacent Strings After Removals

Medium

You are given an array of strings`words`. For each index`i` in the range`[0, words.length - 1]`, perform the following steps:

* Remove the element at index`i` from the`words` array.
* Compute the**length** of the**longest common prefix** among all**adjacent** pairs in the modified array.

Return an array`answer`, where`answer[i]` is the length of the longest common prefix between the adjacent pairs after removing the element at index`i`. If**no** adjacent pairs remain or if**none** share a common prefix, then`answer[i]` should be 0.

**Example 1:**

**Input:** words =["jump","run","run","jump","run"]

**Output:**[3,0,0,3,3]

**Explanation:**

* Removing index 0:
*`words` becomes`["run", "run", "jump", "run"]`
* Longest adjacent pair is`["run", "run"]` having a common prefix`"run"` (length 3)
* Removing index 1:
*`words` becomes`["jump", "run", "jump", "run"]`
* No adjacent pairs share a common prefix (length 0)
* Removing index 2:
*`words` becomes`["jump", "run", "jump", "run"]`
* No adjacent pairs share a common prefix (length 0)
* Removing index 3:
*`words` becomes`["jump", "run", "run", "run"]`
* Longest adjacent pair is`["run", "run"]` having a common prefix`"run"` (length 3)
* Removing index 4:
* words becomes`["jump", "run", "run", "jump"]`
* Longest adjacent pair is`["run", "run"]` having a common prefix`"run"` (length 3)

**Example 2:**

**Input:** words =["dog","racer","car"]

**Output:**[0,0,0]

**Explanation:**

* Removing any index results in an answer of 0.

**Constraints:**

* <code>1 <= words.length <= 10<sup>5</sup></code>
* <code>1 <= words[i].length <= 10<sup>4</sup></code>
*`words[i]` consists of lowercase English letters.
* The sum of`words[i].length` is smaller than or equal <code>10<sup>5</sup></code>.
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
package g3501_3600.s3599_partition_array_to_minimize_xor;

// #Medium #Array #Dynamic_Programming #Bit_Manipulation #Prefix_Sum
// #2025_06_30_Time_144_ms_(100.00%)_Space_44.80_MB_(100.00%)

import java.util.Arrays;

public class Solution {
public int minXor(int[] nums, int k) {
int n = nums.length;
// Step 1: Prefix XOR array
int[] pfix = new int[n + 1];
for (int i = 1; i <= n; i++) {
pfix[i] = pfix[i - 1] ^ nums[i - 1];
}
// Step 2: DP table
int[][] dp = new int[n + 1][k + 1];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
for (int i = 0; i <= n; i++) {
// Base case: 1 partition
dp[i][1] = pfix[i];
}
// Step 3: Fill DP for partitions 2 to k
for (int parts = 2; parts <= k; parts++) {
for (int end = parts; end <= n; end++) {
for (int split = parts - 1; split < end; split++) {
int segmentXOR = pfix[end] ^ pfix[split];
int maxXOR = Math.max(dp[split][parts - 1], segmentXOR);
dp[end][parts] = Math.min(dp[end][parts], maxXOR);
}
}
}
return dp[n][k];
}
}
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
3599\. Partition Array to Minimize XOR

Medium

You are given an integer array`nums` and an integer`k`.

Your task is to partition`nums` into`k` non-empty****non-empty subarrays****. For each subarray, compute the bitwise**XOR** of all its elements.

Return the**minimum** possible value of the**maximum XOR** among these`k` subarrays.

**Example 1:**

**Input:** nums =[1,2,3], k = 2

**Output:** 1

**Explanation:**

The optimal partition is`[1]` and`[2, 3]`.

* XOR of the first subarray is`1`.
* XOR of the second subarray is`2 XOR 3 = 1`.

The maximum XOR among the subarrays is 1, which is the minimum possible.

**Example 2:**

**Input:** nums =[2,3,3,2], k = 3

**Output:** 2

**Explanation:**

The optimal partition is`[2]`,`[3, 3]`, and`[2]`.

* XOR of the first subarray is`2`.
* XOR of the second subarray is`3 XOR 3 = 0`.
* XOR of the third subarray is`2`.

The maximum XOR among the subarrays is 2, which is the minimum possible.

**Example 3:**

**Input:** nums =[1,1,2,3,1], k = 2

**Output:** 0

**Explanation:**

The optimal partition is`[1, 1]` and`[2, 3, 1]`.

* XOR of the first subarray is`1 XOR 1 = 0`.
* XOR of the second subarray is`2 XOR 3 XOR 1 = 0`.

The maximum XOR among the subarrays is 0, which is the minimum possible.

**Constraints:**

*`1 <= nums.length <= 250`
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
*`1 <= k <= n`
Loading
[8]ページ先頭
©2009-2025 Movatter.jp