# Substring Size K

Problem:

Given a string `s` and an int `k`, return all unique substrings of `s` of size `k` with `k` distinct characters.

Example 1:

```Input: s = "abcabc", k = 3
Output: ["abc", "bca", "cab"]

```

Example 2:

```Input: s = "abacab", k = 3
Output: ["bac", "cab"]

```

Example 3:

```Input: s = "awaglknagawunagwkwagl", k = 4
Output: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"]
Explanation:
Substrings in order are: "wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag", "wagl"
"wagl" is repeated twice, but is included in the output once.

```

Constraints:

• The input string consists of only lowercase English letters `[a-z]`
• 0 ≤ `k` ≤ 26

Solution:

Logic:

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

public class SusbstringSizeK {

public static void printUniqueSubstrings(String s, int k) {

if (k <= s.length()) {
Set<Character> uniqueCharacters = new HashSet<>();
Set<String> uniqueSubstrings = new HashSet<>();
for (int i = 0; i <= s.length() - k; i++) {
String shorterString = s.substring(i, i + k);
for (int j = 0; j < k; j++) {
}
if (uniqueCharacters.size() == k) {
}
uniqueCharacters.clear();
}
uniqueSubstrings.stream().forEach(value -> System.out.println(value));
}
}

public static void main(String[] args) {
printUniqueSubstrings("abcabc", 3);
printUniqueSubstrings("awaglknagawunagwkwagl", 4);
}
}
``````

# Partition Labels

A string `S` of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

```Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
```

Note:

• `S` will have length in range `[1, 500]`.
• `S` will consist of lowercase English letters (`'a'` to `'z'`) only.

Solution:

Logic:

``````import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class PartitionLabels {

public static List<Integer> partitionLabels(String S) {
List<Character> values = new ArrayList<>();

for (int i=0; i< S.length(); i++) {
if (!values.contains(S.charAt(i))) {
}
}

List<String> partitions = new ArrayList<>();
int partitionBegin = S.indexOf(values.get(0));
int partitionEnd = S.lastIndexOf(values.get(0));

for(int i=1; i< values.size(); i++) {
int startIndex = S.indexOf(values.get(i));
int endIndex = S.lastIndexOf(values.get(i));
if ((startIndex> partitionEnd)) {
partitionBegin = startIndex;
partitionEnd = endIndex;
} else if (endIndex > partitionEnd) {
partitionEnd = endIndex;
}
}
partitions.stream().forEach(x -> System.out.print(x + " " ));
return partitions.stream().map(x -> x.length()).collect(Collectors.toList());
}

public static void main(String[] args) {
values.stream().forEach(x -> System.out.print(x + " " ));
}
}
``````

# Minimum Cost to Connect Ropes

Problem:

Given `n` ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until `n` ropes are connected into a single rope. Find the min possible cost required to connect all ropes.

Example 1:

```Input: ropes = [8, 4, 6, 12]
Output: 58
Explanation: The optimal way to connect ropes is as follows
1. Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
2. Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
3. Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58

```

Example 2:

```Input: ropes = [20, 4, 8, 2]
Output: 54

```

Example 3:

```Input: ropes = [1, 2, 5, 10, 35, 89]
Output: 224

```

Example 4:

```Input: ropes = [2, 2, 3, 3]
Output: 20
```

Solution:

Logic:

This is rather simple. Here you push all the elements in a PriorityQueue, which on polling will return the values in ascending order (as it applies the natural ordering for integers as priority).

So as you go over the priority queue, you always pick the two smallest rope segments, join them and put them the joined rope segement back in the priority queue..at last you are left with one joined rope segment and one loose rope segment which you join to form the full connected rope and also during the process keep a log of the minimum cost by adding the values to it at every join.

Got that? I would maybe later on do an illustration..that would be fun! For now check out the code below.

``````import java.util.PriorityQueue;

public class MinCostToConnectRopes {

private static int minCost(int[] ropes) {
PriorityQueue<Integer> values = new PriorityQueue<>();
for (int i=0; i<ropes.length; i++) {
values.offer(ropes[i]);
}
int minCost = 0;
while (values.size() != 1) {
int value1 = values.poll();
int value2 = values.poll();
minCost = minCost + value1 + value2;
values.offer(value1 + value2);
}
return minCost;
}

public static void main (String[] args) {
System.out.println(minCost(new int[]{8, 4, 6, 12}));
}
}
``````

# Critical Routers

Problem:

You are given an undirected connected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph.

Input:
The input to the function/method consists of three arguments:

• `numNodes`, an integer representing the number of nodes in the graph.
• `numEdges`, an integer representing the number of edges in the graph.
• `edges`, the list of pair of integers – A, B representing an edge between the nodes A and B.

Output:
Return a list of integers representing the critical nodes.

Example:

```Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]
```

Solution:

Logic:

• First find all the numbers in the connected graph into a unique set
• Order the list of pairs such in ascendence of the first pair element.
• For every element in the unique set,
• find all the connected edges (pairs) which does not contain this element
• Pick the first pair from these and build a list of all the elements that can be reached for this pair.
• Then check if this list size is one less than the size of the unique elements, if so that means the graph is connected, if not then this element is critical. Add this element to the connections set
• Return the list of these connections.

You with me? critical yeah!

``````import java.util.*;

public class CriticalRouters {

public static void main(String[] args) {
List<PairInteger> pairs = new ArrayList<>();

Set<Integer> vertexes = criticalRoutersList(7, 7, pairs);
for (Integer v : vertexes) {
System.out.print(" " + v + ", ");
}

}

public static Set<Integer> criticalRoutersList(int nodesNum, int edgesNum, List<PairInteger> pairs) {
Set<Integer> uniqueSet = new HashSet<>();
Set<Integer> connections = new HashSet<>();
Collections.sort(pairs, (a, b) -> Integer.compare(a.first, b.first));
pairs.stream().forEach(list -> {
});

for (Integer value : uniqueSet) {
List<PairInteger> newPairs = new ArrayList<>();
for (PairInteger paire : pairs) {
if (paire.first != value && paire.second != value) {
}
}
Set<Integer> buildList = new TreeSet<>(Arrays.asList(newPairs.get(0).first, newPairs.get(0).second));
for (int inner = 1; inner < newPairs.size(); inner++) {
mergeTag(buildList, newPairs.get(inner));
}
if (buildList.size() < uniqueSet.size() - 1) {
}
}

return connections;

}

private static void mergeTag(Set<Integer> buildList, PairInteger pairString) {
if (buildList.contains(pairString.first) && buildList.contains(pairString.second))
return;
if (buildList.contains(pairString.first)) {
} else if (buildList.contains(pairString.second)) {
}
}
}

``````
``````public class PairInteger {
int first;
int second;

public PairInteger(int first, int second) {
this.first = first;
this.second = second;
}
}
``````