JetBrains Academy: Hamming distance in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Hamming distance in Java

Finding a substring minimizing distance:

Given two strings, a pattern and a text. Write a program that finds a substring which has the minimum Hamming distance with the pattern.

Input: Two strings, a pattern and a text, each is on a separate line. The length of the text is guaranteed to be no less than the length of the pattern.

Output: Two numbers: the first is the index of an occurrence of the pattern, the second is the Hamming distance between the pattern and a substring which starts from the found index. If there are several substrings with the minimum Hamming distance with the pattern, print the index of the first one.

import java.util.*;

public class Main {
    public static void main(String[] args) {        
        Scanner scanner = new Scanner(System.in);
        String pattern = scanner.nextLine();
        String text = scanner.nextLine();
        
        Hamming hamming = Hamming.substringHamming(pattern, text);
        System.out.println(hamming.toString());
    }
}

class Hamming {
    public int index = -1;
    public int distance;

    public Hamming(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public static int hammingDistance(String s, String t) {
        int hammingDist = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                hammingDist += 1;
            }
        }

        return hammingDist;
    }

    public static Hamming substringHamming(String s, String t) {
        int index = -1;
        int minD = Integer.MAX_VALUE;
        int l = s.length();

        for (int i = 0; i <= t.length() - l; i++) {
            int d = hammingDistance(s, t.substring(i, i + l));
            if (d < minD) {
                minD = d;
                index = i;
            }
        }

        return new Hamming(index, minD);
    }

    @Override
    public String toString() {
        return String.format("%d %d", index, distance);
    }
}

---

Finding a reverse substring:

Given two strings of equal length (denoted as s and t) and an integer k. Write a program that finds the index i such that the Hamming distance between reverse(s[i:k]) and t[i:k] is the minimal.

Input: Two strings of equal length and an integer k.

Output: Two numbers: the first is the index ii satisfying the conditions above, the second is the Hamming distance between corresponding substrings. If there are several such indexes, print the minimal one.

import java.util.*;

public class Main {
    public static void main(String[] args) { 
        Scanner scanner = new Scanner(System.in);       
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        int k = Integer.parseInt(scanner.nextLine());

        Hamming hamming = Hamming.reverse(s, t, k);
        System.out.println(hamming.toString());
    }
}

class Hamming {
    public int index = -1;
    public int distance;

    public Hamming(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public static int hammingDistance(String s, String t) {
        int hammingDist = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                hammingDist += 1;
            }
        }

        return hammingDist;
    }

    public static Hamming reverse(String s, String t, int k) {
        int index = -1;
        int d = Integer.MAX_VALUE;
        
        if (s.length() == 0) {
            return new Hamming(0, 0);
        }

        for (int i = 0; i <= s.length() - k; i++) {
            StringBuilder reversedSub = new StringBuilder(s.substring(i, i + k)).reverse();
            String reversed = reversedSub.toString();
            String sub = t.substring(i, i + k);
            int hD = hammingDistance(reversed, sub);

            if (hD < d) {
                d = hD;
                index = i;
            }
        }

        return new Hamming(index, d);
    }
    
    @Override
    public String toString() {
        return String.format("%d %d", index, distance);
    }
}

---

Finding a representative of strings:

Consider a collection of strings of equal length. Let's call a string a representative if it has the minimum sum of Hamming distances with all other strings from the collection. Write a program that finds a representative for a collection of strings of equal length.

Input: An integer k>1 and a collection of k strings of equal length, each is on a separate line.

Output: A representative of a given collection of strings. If there are several representatives, print the one that has the least index (assuming that the first string has an index 1, the second string has an index 2 and so on).

import java.util.*;

public class Main {
    public static void main(String[] args) {        
        Scanner scanner = new Scanner(System.in);
        int k = Integer.parseInt(scanner.nextLine());
        String[] array = new String[k];
        for (int i = 0; i < k; i++) {
            array[i] = scanner.nextLine();
        }
        
        Hamming hamming = Hamming.representative(array);
        System.out.println(array[hamming.index]);
    }
}

class Hamming {
    public int index = -1;
    public int distance;

    public Hamming(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public static int hammingDistance(String s, String t) {
        int hammingDist = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                hammingDist += 1;
            }
        }

        return hammingDist;
    }

    public static Hamming representative(String[] array) {
        int index = -1;
        int sumOfMinD = Integer.MAX_VALUE;

        for (int i = 0; i < array.length; i++) {
            int sum = 0;
            for (String s : array) {
                int hammingDistance = hammingDistance(array[i], s);
                sum += hammingDistance;
            }
            if (sum < sumOfMinD) {
                sumOfMinD = sum;
                index = i;
            }
        }

        return new Hamming(index, sumOfMinD);
    }
}

---