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++) {
                    uniqueCharacters.add(shorterString.charAt(j));
                }
                if (uniqueCharacters.size() == k) {
                    uniqueSubstrings.add(shorterString);
                }
                uniqueCharacters.clear();
            }
            uniqueSubstrings.stream().forEach(value -> System.out.println(value));
        }
    }

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

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}));
    }
}

TapeEquillibrium

Solution:

This java solution to the codility problem TapeEquillibrium scored 100%

Logic: First find the sum of all the integers in the array. Then start to iterate over from first partition point being the first position until the second last item and calculate the left sum and the right sum. Find the difference between them and compare it with the minimum difference so far calculated, if its less than that then set the minimum difference to this new lower value..continue.

With the end of the for loop the correct minimum difference is reached. Return that!

Also check out the Math functions..they are so convenient! abs and min!

    public int solution(int[] A) {
        long totalSum=0;
        int minDifference = Integer.MAX_VALUE;
        for (int i=0; i<A.length;i++) {
            totalSum = totalSum + A[i];
        }
        long leftSum = 0;
        long rightSum = 0;
        for (int i=0; i<A.length - 1; i++) {
            leftSum = leftSum + A[i];
            rightSum = totalSum - leftSum;
            int currentDifference = (int) Math.abs(leftSum - rightSum);
            minDifference = Math.min(currentDifference, minDifference);
        }
        return minDifference;
    }

PermMissingElem

Solution:

This java solution to codility problem PermMissingElem scored a 100%

Logic: Iterate over the array and add the elements to a set on which you can do a contains operation. Iterate over the hashset for the first n+1 numbers and if when a specific number is not found in the hashset then that is the missing element.

import java.util.HashSet;
import java.util.Set;
class PermMissingElement{
    public int solution(int[] A) {
        int n = A.length + 1;
        int missingNumber = 0;
        Set<Integer> values = new HashSet<>();
        for (int i=0; i<A.length; i++) {
            values.add(A[i]);
        }
        for (int i=1; i<=n; i++) {
            if (!values.contains(i)) {
                missingNumber = i;
            }
        }
        return missingNumber;
    }
}

Solution 2:

This java solution scored 80% as it failed with larger length (~100,000)

Logic: Calculate the sum of the first n+1 natural numbers. Then iterate over the array and deduct the value from the sum. Whats left of the sum is the missing number. But aha fails with bigger ranges..

    
class PermMissingElement{
   public int solution1(int[] A) {

        int n = A.length + 1;
        long sumOfFirstN = n * (n+1)/2;
        for (int i=0; i<A.length; i++) {
            sumOfFirstN = sumOfFirstN - A[i];
        }
        return (int)(sumOfFirstN);
    }
}