packageg2701_2800.s2707_extra_characters_in_a_string;

importjava.util.Arrays;

publicclassSolution {

publicintminExtraChar(Strings,String[]dictionary) {

returntabulationApproach(s,dictionary);

}

privateinttabulationApproach(Strings,String[]dictionary) {

intm =s.length();

int[]dp =newint[m +1];

for (inti =m -1;i >=0;i--) {

dp[i] =dp[i +1] +1;

intfinalI =i;

Arrays.stream(dictionary)

.filter(word ->s.startsWith(word,finalI))

.mapToInt(String::length)

.map(n ->dp[finalI +n])

.forEach(prev ->dp[finalI] =Math.min(dp[finalI],prev));

}

returndp[0];

}

}

2707\. Extra Characters in a String

Medium

You are given a**0-indexed** string`s` and a dictionary of words`dictionary`. You have to break`s` into one or more**non-overlapping** substrings such that each substring is present in`dictionary`. There may be some**extra characters** in`s` which are not present in any of the substrings.

Return_the**minimum** number of extra characters left over if you break up_`s`_optimally._

**Example 1:**

**Input:** s = "leetscode", dictionary =["leet","code","leetcode"]

**Output:** 1

**Explanation:** We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

**Example 2:**

**Input:** s = "sayhelloworld", dictionary =["hello","world"]

**Output:** 3

**Explanation:** We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

**Constraints:**

*`dictionary[i]` and`s` consists of only lowercase English letters

*`dictionary` contains distinct words

packageg2701_2800.s2708_maximum_strength_of_a_group;

importjava.util.ArrayList;

importjava.util.List;

publicclassSolution {

publiclongmaxStrength(int[]nums) {

List<Integer>filtered =newArrayList<>();

longproduct =1L;

booleanhasZero =false;

for (intnum :nums) {

if (num ==0) {

hasZero =true;

continue;

}

filtered.add(num);

product *=num;

}

if (filtered.isEmpty()) {

return0;

}

if (filtered.size() ==1 &&filtered.get(0) <=0) {

returnhasZero ?0 :filtered.get(0);

}

longresult =product;

for (intnum :nums) {

if (num ==0) {

continue;

}

result =Math.max(result,product /num);

}

returnresult;

}

}

2708\. Maximum Strength of a Group

Medium

You are given a**0-indexed** integer array`nums` representing the score of students in an exam. The teacher would like to form one**non-empty** group of students with maximal**strength**, where the strength of a group of students of indices <code>i₀</code>, <code>i₁</code>, <code>i₂</code>, ... , <code>i_k</code> is defined as <code>nums[i₀] * nums[i₁] * nums[i₂] * ... * nums[i_k]</code>.

Return_the maximum strength of a group the teacher can create_.

**Example 1:**

**Input:** nums =[3,-1,-5,2,5,-9]

**Output:** 1350

**Explanation:** One way to form a group of maximal strength is to group the students at indices[0,2,3,4,5]. Their strength is 3\* (-5)\* 2\* 5\* (-9) = 1350, which we can show is optimal.

**Example 2:**

**Input:** nums =[-4,-5,-4]

**Output:** 20

**Explanation:** Group the students at indices[0, 1] . Then, we’ll have a resulting strength of 20. We cannot achieve greater strength.

**Constraints:**

packageg2701_2800.s2709_greatest_common_divisor_traversal;

importjava.util.HashMap;

importjava.util.Map;

publicclassSolution {

privateMap<Integer,Integer>map =null;

privateint[]set;

privateintfindParent(intu) {

if (u ==set[u]) {

returnu;

}

set[u] =findParent(set[u]);

returnset[u];

}

privatevoidunion(inta,intb) {

intp1 =findParent(a);

intp2 =findParent(b);

if (p1 !=p2) {

set[b] =p1;

}

set[p2] =p1;

}

privatevoidsolve(intn,intindex) {

if (n %2 ==0) {

intx =map.getOrDefault(2, -1);

if (x != -1) {

union(x,index);

}

while (n %2 ==0) {

n /=2;

}

map.put(2,index);

}

intsqrt = (int)Math.sqrt(n);

for (inti =3;i <=sqrt;i++) {

if (n %i ==0) {

intx =map.getOrDefault(i, -1);

if (x != -1) {

union(x,index);

}

while (n %i ==0) {

n /=i;

}

map.put(i,index);

}

}

if (n >2) {

intx =map.getOrDefault(n, -1);

if (x != -1) {

union(x,index);

}

map.put(n,index);

}

}

publicbooleancanTraverseAllPairs(int[]nums) {

set =newint[nums.length];

map =newHashMap<>();

for (inti =0;i <nums.length;i++) {

set[i] =i;

}

for (inti =0;i <nums.length;i++) {

solve(nums[i],i);

}

intp =findParent(0);

for (inti =0;i <nums.length;i++) {

if (p !=findParent(i)) {

returnfalse;

}

}

returntrue;

}

}

2709\. Greatest Common Divisor Traversal

Hard

You are given a**0-indexed** integer array`nums`, and you are allowed to**traverse** between its indices. You can traverse between index`i` and index`j`,`i != j`, if and only if`gcd(nums[i], nums[j]) > 1`, where`gcd` is the**greatest common divisor**.

Your task is to determine if for**every pair** of indices`i` and`j` in nums, where`i < j`, there exists a**sequence of traversals** that can take us from`i` to`j`.

Return`true`_if it is possible to traverse between all such pairs of indices,__or_`false`_otherwise._

**Example 1:**

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

**Output:** true

**Explanation:** In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2). To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1. To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.

**Example 2:**

**Input:** nums =[3,9,5]

**Output:** false

**Explanation:** No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.

**Example 3:**

**Input:** nums =[4,3,12,8]

**Output:** true

**Explanation:** There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.

**Constraints:**

* <code>1 <= nums.length <= 10⁵</code>

* <code>1 <= nums[i] <= 10⁵</code>

packageg2701_2800.s2710_remove_trailing_zeros_from_a_string;

publicclassSolution {

publicStringremoveTrailingZeros(Stringnum) {

intendIndex =num.length() -1;

while (endIndex >=0 &&num.charAt(endIndex) =='0') {

endIndex--;

}

returnnum.substring(0,endIndex +1);

}

}

2710\. Remove Trailing Zeros From a String

Easy

Given a**positive** integer`num` represented as a string, return_the integer_`num`_without trailing zeros as a string_.

**Example 1:**

**Input:** num = "51230100"

**Output:** "512301"

**Explanation:** Integer "51230100" has 2 trailing zeros, we remove them and return integer "512301".

**Example 2:**

**Input:** num = "123"

**Output:** "123"

**Explanation:** Integer "123" has no trailing zeros, we return integer "123".

**Constraints:**

*`num` consists of only digits.

*`num` doesn't have any leading zeros.

packageg2701_2800.s2711_difference_of_number_of_distinct_values_on_diagonals;

importjava.util.HashSet;

importjava.util.Set;

publicclassSolution {

publicint[][]differenceOfDistinctValues(int[][]grid) {

intm =grid.length;

intn =grid[0].length;

int[][]arrTopLeft =newint[m][n];

int[][]arrBotRight =newint[m][n];

for (inti =m -1;i >=0;i--) {

intc =0;

intr =i;

Set<Integer>set =newHashSet<>();

while (cellExists(r,c,grid)) {

arrTopLeft[r][c] =set.size();

set.add(grid[r++][c++]);

}

}

for (inti =1;i <n;i++) {

intr =0;

intc =i;

Set<Integer>set =newHashSet<>();

while (cellExists(r,c,grid)) {

arrTopLeft[r][c] =set.size();

set.add(grid[r++][c++]);

}

}

for (inti =0;i <n;i++) {

intr =m -1;

intc =i;

Set<Integer>set =newHashSet<>();

while (cellExists(r,c,grid)) {

arrBotRight[r][c] =set.size();

set.add(grid[r--][c--]);

}

}

for (inti =m -1;i >=0;i--) {

intc =n -1;

intr =i;

Set<Integer>set =newHashSet<>();

while (cellExists(r,c,grid)) {

arrBotRight[r][c] =set.size();

set.add(grid[r--][c--]);

}

}

int[][]result =newint[m][n];

for (intr =0;r <m;r++) {

for (intc =0;c <n;c++) {

result[r][c] =Math.abs(arrTopLeft[r][c] -arrBotRight[r][c]);

}

}

returnresult;

}

privatebooleancellExists(intr,intc,int[][]grid) {

returnr >=0 &&r <grid.length &&c >=0 &&c <grid[0].length;

}

}