May 27, 2025 · May 25, 2025 · May 25, 2025 · May 25, 2025 · May 25, 2025 · May 25, 2025
diff --git a/src/main/java/g3501_3600/s3556_sum_of_largest_prime_substrings/Solution.java b/src/main/java/g3501_3600/s3556_sum_of_largest_prime_substrings/Solution.java
 package g3501_3600.s3556_sum_of_largest_prime_substrings;

 // #Medium #String #Hash_Table #Math #Sorting #Number_Theory
 // #2025_05_27_Time_7_ms_(99.93%)_Space_42.77_MB_(98.34%)

 import java.util.HashSet;
 import java.util.Set;

 public class Solution {
    public long sumOfLargestPrimes(String s) {
        Set<Long> set = new HashSet<>();
        int n = s.length();
        long first = -1;
        long second = -1;
        long third = -1;
        for (int i = 0; i < n; i++) {
            long num = 0;
            for (int j = i; j < n; j++) {
                num = num * 10 + (s.charAt(j) - '0');
                if (i != j && s.charAt(i) == '0') {
                    break;
                }
                if (isPrime(num) && !set.contains(num)) {
                    set.add(num);
                    if (num > first) {
                        third = second;
                        second = first;
                        first = num;
                    } else if (num > second) {
                        third = second;
                        second = num;
                    } else if (num > third) {
                        third = num;
                    }
                }
            }
        }
        long sum = 0;
        if (first != -1) {
            sum += first;
        }
        if (second != -1) {
            sum += second;
        }
        if (third != -1) {
            sum += third;
        }
        return sum;
    }

    public boolean isPrime(long num) {
        if (num <= 1) {
            return false;
        }
        if (num == 2 || num == 3) {
            return true;
        }
        if (num % 2 == 0 || num % 3 == 0) {
            return false;
        }
        for (long i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
 }
diff --git a/src/main/java/g3501_3600/s3556_sum_of_largest_prime_substrings/readme.md b/src/main/java/g3501_3600/s3556_sum_of_largest_prime_substrings/readme.md
 3556\. Sum of Largest Prime Substrings

 Medium

 Given a string `s`, find the sum of the **3 largest unique prime numbers** that can be formed using any of its ****substring****.

 Return the **sum** of the three largest unique prime numbers that can be formed. If fewer than three exist, return the sum of **all** available primes. If no prime numbers can be formed, return 0.

 **Note:** Each prime number should be counted only **once**, even if it appears in **multiple** substrings. Additionally, when converting a substring to an integer, any leading zeros are ignored.

 **Example 1:**

 **Input:** s = "12234"

 **Output:** 1469

 **Explanation:**

 *   The unique prime numbers formed from the substrings of `"12234"` are 2, 3, 23, 223, and 1223.
 *   The 3 largest primes are 1223, 223, and 23. Their sum is 1469.

 **Example 2:**

 **Input:** s = "111"

 **Output:** 11

 **Explanation:**

 *   The unique prime number formed from the substrings of `"111"` is 11.
 *   Since there is only one prime number, the sum is 11.

 **Constraints:**

 *   `1 <= s.length <= 10`
 *   `s` consists of only digits.
diff --git a/...in/java/g3501_3600/s3557_find_maximum_number_of_non_intersecting_substrings/Solution.java b/...in/java/g3501_3600/s3557_find_maximum_number_of_non_intersecting_substrings/Solution.java
 package g3501_3600.s3557_find_maximum_number_of_non_intersecting_substrings;

 // #Medium #String #Hash_Table #Dynamic_Programming #Greedy
 // #2025_05_27_Time_15_ms_(84.54%)_Space_45.82_MB_(91.39%)

 import java.util.Arrays;

 public class Solution {
    public int maxSubstrings(String s) {
        int[] prev = new int[26];
        int r = 0;
        Arrays.fill(prev, -1);
        for (int i = 0; i < s.length(); ++i) {
            int j = s.charAt(i) - 'a';
            if (prev[j] != -1 && i - prev[j] + 1 >= 4) {
                ++r;
                Arrays.fill(prev, -1);
            } else if (prev[j] == -1) {
                prev[j] = i;
            }
        }
        return r;
    }
 }
diff --git a/...a/g3501_3600/s3557_find_maximum_number_of_non_intersecting_substrings/readme.md b/...a/g3501_3600/s3557_find_maximum_number_of_non_intersecting_substrings/readme.md
 3557\. Find Maximum Number of Non Intersecting Substrings

 Medium

 You are given a string `word`.

 Return the **maximum** number of non-intersecting ****substring**** of word that are at **least** four characters long and start and end with the same letter.

 **Example 1:**

 **Input:** word = "abcdeafdef"

 **Output:** 2

 **Explanation:**

 The two substrings are `"abcdea"` and `"fdef"`.

 **Example 2:**

 **Input:** word = "bcdaaaab"

 **Output:** 1

 **Explanation:**

 The only substring is `"aaaa"`. Note that we cannot **also** choose `"bcdaaaab"` since it intersects with the other substring.

 **Constraints:**

 *   <code>1 <= word.length <= 2 * 10<sup>5</sup></code>
 *   `word` consists only of lowercase English letters.
diff --git a/src/main/java/g3501_3600/s3558_number_of_ways_to_assign_edge_weights_i/Solution.java b/src/main/java/g3501_3600/s3558_number_of_ways_to_assign_edge_weights_i/Solution.java
 package g3501_3600.s3558_number_of_ways_to_assign_edge_weights_i;

 // #Medium #Math #Tree #Depth_First_Search #2025_05_27_Time_12_ms_(100.00%)_Space_106.62_MB_(76.01%)

 public class Solution {
    private static int mod = (int) 1e9 + 7;
    private long[] pow2 = new long[100001];

    public int assignEdgeWeights(int[][] edges) {
        if (pow2[0] == 0) {
            pow2[0] = 1;
            for (int i = 1; i < pow2.length; i++) {
                pow2[i] = (pow2[i - 1] << 1) % mod;
            }
        }
        int n = edges.length + 1;
        int[] adj = new int[n + 1];
        int[] degrees = new int[n + 1];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u] += v;
            adj[v] += u;
            degrees[u]++;
            degrees[v]++;
        }
        int[] que = new int[n];
        int write = 0;
        int read = 0;
        for (int i = 2; i <= n; ++i) {
            if (degrees[i] == 1) {
                que[write++] = i;
            }
        }
        int distance = 0;
        while (read < write) {
            distance++;
            int size = write - read;
            while (size-- > 0) {
                int v = que[read++];
                int u = adj[v];
                adj[u] -= v;
                if (--degrees[u] == 1 && u != 1) {
                    que[write++] = u;
                }
            }
        }
        return (int) pow2[distance - 1];
    }
 }
diff --git a/src/main/java/g3501_3600/s3558_number_of_ways_to_assign_edge_weights_i/readme.md b/src/main/java/g3501_3600/s3558_number_of_ways_to_assign_edge_weights_i/readme.md
 3558\. Number of Ways to Assign Edge Weights I

 Medium

 There is an undirected tree with `n` nodes labeled from 1 to `n`, rooted at node 1. The tree is represented by a 2D integer array `edges` of length `n - 1`, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code>.

 Initially, all edges have a weight of 0. You must assign each edge a weight of either **1** or **2**.

 The **cost** of a path between any two nodes `u` and `v` is the total weight of all edges in the path connecting them.

 Select any one node `x` at the **maximum** depth. Return the number of ways to assign edge weights in the path from node 1 to `x` such that its total cost is **odd**.

 Since the answer may be large, return it **modulo** <code>10<sup>9</sup> + 7</code>.

 **Note:** Ignore all edges **not** in the path from node 1 to `x`.

 **Example 1:**

 ![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-060006.png)

 **Input:** edges = [[1,2]]

 **Output:** 1

 **Explanation:**

 *   The path from Node 1 to Node 2 consists of one edge (`1 → 2`).
 *   Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.

 **Example 2:**

 ![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-055820.png)

 **Input:** edges = [[1,2],[1,3],[3,4],[3,5]]

 **Output:** 2

 **Explanation:**

 *   The maximum depth is 2, with nodes 4 and 5 at the same depth. Either node can be selected for processing.
 *   For example, the path from Node 1 to Node 4 consists of two edges (`1 → 3` and `3 → 4`).
 *   Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.

 **Constraints:**

 *   <code>2 <= n <= 10<sup>5</sup></code>
 *   `edges.length == n - 1`
 *   <code>edges[i] == [u<sub>i</sub>, v<sub>i</sub>]</code>
 *   <code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code>
 *   `edges` represents a valid tree.
diff --git a/src/main/java/g3501_3600/s3559_number_of_ways_to_assign_edge_weights_ii/Solution.java b/src/main/java/g3501_3600/s3559_number_of_ways_to_assign_edge_weights_ii/Solution.java
 package g3501_3600.s3559_number_of_ways_to_assign_edge_weights_ii;

 // #Hard #Array #Dynamic_Programming #Math #Tree #Depth_First_Search
 // #2025_05_27_Time_138_ms_(64.66%)_Space_133.20_MB_(11.56%)

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

 public class Solution {
    private static final int MOD = 1000000007;
    private List<List<Integer>> adj;
    private int[] level;
    private int[][] jumps;

    private void mark(int node, int par) {
        for (int neigh : adj.get(node)) {
            if (neigh == par) {
                continue;
            }
            level[neigh] = level[node] + 1;
            jumps[neigh][0] = node;
            mark(neigh, node);
        }
    }

    public int lift(int u, int diff) {
        while (diff > 0) {
            int rightmost = diff ^ (diff & (diff - 1));
            int jump = (int) (Math.log(rightmost) / Math.log(2));
            u = jumps[u][jump];
            diff -= rightmost;
        }
        return u;
    }

    private int findLca(int u, int v) {
        if (level[u] > level[v]) {
            int temp = u;
            u = v;
            v = temp;
        }
        v = lift(v, level[v] - level[u]);
        if (u == v) {
            return u;
        }
        for (int i = jumps[0].length - 1; i >= 0; i--) {
            if (jumps[u][i] != jumps[v][i]) {
                u = jumps[u][i];
                v = jumps[v][i];
            }
        }
        return jumps[u][0];
    }

    private int findDist(int a, int b) {

        return level[a] + level[b] - 2 * level[findLca(a, b)];
    }

    public int[] assignEdgeWeights(int[][] edges, int[][] queries) {
        int n = edges.length + 1;
        adj = new ArrayList<>();
        level = new int[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] i : edges) {
            adj.get(i[0] - 1).add(i[1] - 1);
            adj.get(i[1] - 1).add(i[0] - 1);
        }
        int m = (int) (Math.ceil(Math.log(n - 1.0) / Math.log(2))) + 1;
        jumps = new int[n][m];
        mark(0, -1);
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                int p = jumps[i][j - 1];
                jumps[i][j] = jumps[p][j - 1];
            }
        }
        int[] pow = new int[n + 1];
        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow[i] = (pow[i - 1] * 2) % MOD;
        }
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int d = findDist(queries[i][0] - 1, queries[i][1] - 1);
            ans[i] = d > 0 ? pow[d - 1] : 0;
        }
        return ans;
    }
 }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,68 @@
		package g3501_3600.s3556_sum_of_largest_prime_substrings;

		// #Medium #String #Hash_Table #Math #Sorting #Number_Theory
		// #2025_05_27_Time_7_ms_(99.93%)_Space_42.77_MB_(98.34%)

		import java.util.HashSet;
		import java.util.Set;

		public class Solution {
		public long sumOfLargestPrimes(String s) {
		Set<Long> set = new HashSet<>();
		int n = s.length();
		long first = -1;
		long second = -1;
		long third = -1;
		for (int i = 0; i < n; i++) {
		long num = 0;
		for (int j = i; j < n; j++) {
		num = num * 10 + (s.charAt(j) - '0');
		if (i != j && s.charAt(i) == '0') {
		break;
		}
		if (isPrime(num) && !set.contains(num)) {
		set.add(num);
		if (num > first) {
		third = second;
		second = first;
		first = num;
		} else if (num > second) {
		third = second;
		second = num;
		} else if (num > third) {
		third = num;
		}
		}
		}
		}
		long sum = 0;
		if (first != -1) {
		sum += first;
		}
		if (second != -1) {
		sum += second;
		}
		if (third != -1) {
		sum += third;
		}
		return sum;
		}

		public boolean isPrime(long num) {
		if (num <= 1) {
		return false;
		}
		if (num == 2 \|\| num == 3) {
		return true;
		}
		if (num % 2 == 0 \|\| num % 3 == 0) {
		return false;
		}
		for (long i = 5; i * i <= num; i += 6) {
		if (num % i == 0 \|\| num % (i + 2) == 0) {
		return false;
		}
		}
		return true;
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,36 @@
		3556\. Sum of Largest Prime Substrings

		Medium

		Given a string `s`, find the sum of the 3 largest unique prime numbers that can be formed using any of its **substring**.

		Return the sum of the three largest unique prime numbers that can be formed. If fewer than three exist, return the sum of all available primes. If no prime numbers can be formed, return 0.

		Note: Each prime number should be counted only once, even if it appears in multiple substrings. Additionally, when converting a substring to an integer, any leading zeros are ignored.

		Example 1:

		Input: s = "12234"

		Output: 1469

		Explanation:

		* The unique prime numbers formed from the substrings of `"12234"` are 2, 3, 23, 223, and 1223.
		* The 3 largest primes are 1223, 223, and 23. Their sum is 1469.

		Example 2:

		Input: s = "111"

		Output: 11

		Explanation:

		* The unique prime number formed from the substrings of `"111"` is 11.
		* Since there is only one prime number, the sum is 11.

		Constraints:

		* `1 <= s.length <= 10`
		* `s` consists of only digits.
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,24 @@
		package g3501_3600.s3557_find_maximum_number_of_non_intersecting_substrings;

		// #Medium #String #Hash_Table #Dynamic_Programming #Greedy
		// #2025_05_27_Time_15_ms_(84.54%)_Space_45.82_MB_(91.39%)

		import java.util.Arrays;

		public class Solution {
		public int maxSubstrings(String s) {
		int[] prev = new int[26];
		int r = 0;
		Arrays.fill(prev, -1);
		for (int i = 0; i < s.length(); ++i) {
		int j = s.charAt(i) - 'a';
		if (prev[j] != -1 && i - prev[j] + 1 >= 4) {
		++r;
		Arrays.fill(prev, -1);
		} else if (prev[j] == -1) {
		prev[j] = i;
		}
		}
		return r;
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,32 @@
		3557\. Find Maximum Number of Non Intersecting Substrings

		Medium

		You are given a string `word`.

		Return the maximum number of non-intersecting **substring of word that are at least** four characters long and start and end with the same letter.

		Example 1:

		Input: word = "abcdeafdef"

		Output: 2

		Explanation:

		The two substrings are `"abcdea"` and `"fdef"`.

		Example 2:

		Input: word = "bcdaaaab"

		Output: 1

		Explanation:

		The only substring is `"aaaa"`. Note that we cannot also choose `"bcdaaaab"` since it intersects with the other substring.

		Constraints:

		* <code>1 <= word.length <= 2 * 10<sup>5</sup></code>
		* `word` consists only of lowercase English letters.
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,50 @@
		package g3501_3600.s3558_number_of_ways_to_assign_edge_weights_i;

		// #Medium #Math #Tree #Depth_First_Search #2025_05_27_Time_12_ms_(100.00%)_Space_106.62_MB_(76.01%)

		public class Solution {
		private static int mod = (int) 1e9 + 7;
		private long[] pow2 = new long[100001];

		public int assignEdgeWeights(int[][] edges) {
		if (pow2[0] == 0) {
		pow2[0] = 1;
		for (int i = 1; i < pow2.length; i++) {
		pow2[i] = (pow2[i - 1] << 1) % mod;
		}
		}
		int n = edges.length + 1;
		int[] adj = new int[n + 1];
		int[] degrees = new int[n + 1];
		for (int[] edge : edges) {
		int u = edge[0];
		int v = edge[1];
		adj[u] += v;
		adj[v] += u;
		degrees[u]++;
		degrees[v]++;
		}
		int[] que = new int[n];
		int write = 0;
		int read = 0;
		for (int i = 2; i <= n; ++i) {
		if (degrees[i] == 1) {
		que[write++] = i;
		}
		}
		int distance = 0;
		while (read < write) {
		distance++;
		int size = write - read;
		while (size-- > 0) {
		int v = que[read++];
		int u = adj[v];
		adj[u] -= v;
		if (--degrees[u] == 1 && u != 1) {
		que[write++] = u;
		}
		}
		}
		return (int) pow2[distance - 1];
		}
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,50 @@
		3558\. Number of Ways to Assign Edge Weights I

		Medium

		There is an undirected tree with `n` nodes labeled from 1 to `n`, rooted at node 1. The tree is represented by a 2D integer array `edges` of length `n - 1`, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code>.

		Initially, all edges have a weight of 0. You must assign each edge a weight of either 1 or 2.

		The cost of a path between any two nodes `u` and `v` is the total weight of all edges in the path connecting them.

		Select any one node `x` at the maximum depth. Return the number of ways to assign edge weights in the path from node 1 to `x` such that its total cost is odd.

		Since the answer may be large, return it modulo <code>10<sup>9</sup> + 7</code>.

		Note: Ignore all edges not in the path from node 1 to `x`.

		Example 1:

		![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-060006.png)

		Input: edges = [[1,2]]

		Output: 1

		Explanation:

		* The path from Node 1 to Node 2 consists of one edge (`1 → 2`).
		* Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.

		Example 2:

		![](https://assets.leetcode.com/uploads/2025/03/23/screenshot-2025-03-24-at-055820.png)

		Input: edges = [[1,2],[1,3],[3,4],[3,5]]

		Output: 2

		Explanation:

		* The maximum depth is 2, with nodes 4 and 5 at the same depth. Either node can be selected for processing.
		* For example, the path from Node 1 to Node 4 consists of two edges (`1 → 3` and `3 → 4`).
		* Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.

		Constraints:

		* <code>2 <= n <= 10<sup>5</sup></code>
		* `edges.length == n - 1`
		* <code>edges[i] == [u<sub>i</sub>, v<sub>i</sub>]</code>
		* <code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code>
		* `edges` represents a valid tree.
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,93 @@
		package g3501_3600.s3559_number_of_ways_to_assign_edge_weights_ii;

		// #Hard #Array #Dynamic_Programming #Math #Tree #Depth_First_Search
		// #2025_05_27_Time_138_ms_(64.66%)_Space_133.20_MB_(11.56%)

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

		public class Solution {
		private static final int MOD = 1000000007;
		private List<List<Integer>> adj;
		private int[] level;
		private int[][] jumps;

		private void mark(int node, int par) {
		for (int neigh : adj.get(node)) {
		if (neigh == par) {
		continue;
		}
		level[neigh] = level[node] + 1;
		jumps[neigh][0] = node;
		mark(neigh, node);
		}
		}

		public int lift(int u, int diff) {
		while (diff > 0) {
		int rightmost = diff ^ (diff & (diff - 1));
		int jump = (int) (Math.log(rightmost) / Math.log(2));
		u = jumps[u][jump];
		diff -= rightmost;
		}
		return u;
		}

		private int findLca(int u, int v) {
		if (level[u] > level[v]) {
		int temp = u;
		u = v;
		v = temp;
		}
		v = lift(v, level[v] - level[u]);
		if (u == v) {
		return u;
		}
		for (int i = jumps[0].length - 1; i >= 0; i--) {
		if (jumps[u][i] != jumps[v][i]) {
		u = jumps[u][i];
		v = jumps[v][i];
		}
		}
		return jumps[u][0];
		}

		private int findDist(int a, int b) {

		return level[a] + level[b] - 2 * level[findLca(a, b)];
		}

		public int[] assignEdgeWeights(int[][] edges, int[][] queries) {
		int n = edges.length + 1;
		adj = new ArrayList<>();
		level = new int[n];
		for (int i = 0; i < n; i++) {
		adj.add(new ArrayList<>());
		}
		for (int[] i : edges) {
		adj.get(i[0] - 1).add(i[1] - 1);
		adj.get(i[1] - 1).add(i[0] - 1);
		}
		int m = (int) (Math.ceil(Math.log(n - 1.0) / Math.log(2))) + 1;
		jumps = new int[n][m];
		mark(0, -1);
		for (int j = 1; j < m; j++) {
		for (int i = 0; i < n; i++) {
		int p = jumps[i][j - 1];
		jumps[i][j] = jumps[p][j - 1];
		}
		}
		int[] pow = new int[n + 1];
		pow[0] = 1;
		for (int i = 1; i <= n; i++) {
		pow[i] = (pow[i - 1] * 2) % MOD;
		}
		int q = queries.length;
		int[] ans = new int[q];
		for (int i = 0; i < q; i++) {
		int d = findDist(queries[i][0] - 1, queries[i][1] - 1);
		ans[i] = d > 0 ? pow[d - 1] : 0;
		}
		return ans;
		}
		}